Алгебра высказываний

Алгебра высказываний ( алгебра логики ) – раздел математической логики, изучающий строение сложных логических высказываний и способы установления их истинности или ложности с помощью алгебраических методов.

Логическая переменная – простое высказывание, содержащее только одну мысль. ( обозначение – латинские буквы ).

Может принимать лишь два значения:

«истина» (1) и «ложь» (0).

Например: А = 1, В = 0

- составное высказывание,

в котором простые

высказывания связаны

между собой логическими

операциями.

Обозначение - F(A, B,..)

Существуют базовые логические операции:

конъюнкция, дизъюнкция, отрицание и дополнительные :

импликация и эквивалентность

Если составное высказывание (логическую функцию) выразить в виде формулы, то получиться логическое выражение , значение которого можно вычислить. Значением могут быть только ЛОЖЬ или ИСТИНА.

Конъюнкция

Название

Дизъюнкция

Обозначение

Инверсия

Союз в естеств. языке и в программир.

Импликация

Диаграмма Эйлера-Венна

Таблица истинности

Эквивалентность

схемы

От латинского conjunctio - связывать.

«И»

AND

A & B, A ^ B, A * B

Диаграмма Эйлера-Венна:

B

A&B

A

0 0 0 0 1 0 1 0 0 1 1 1

&

Y=A&B

В

А

От латинского disjunction - различаю.

«Или»

OR

A v B, A + B

Диаграмма Эйлера-Венна:

AvB

B

A

А

В

0 0 0 0 1 1 1 0 1 1 1 1

A

1

Y=AvB

В

А

В

От латинского inversio - переворачиваю.

«Не»

NOT

_ A, A

_A

1

A

_A

Диаграмма Эйлера-Венна:

A

_ A A

_

A

0 1 1 0

_A

А

A

От латинского implicatio - тесно связываю.

«Если …, то .. .»

« If … then .. .»

A B

A B

B

A

0 0 1 0 1 1 1 0 0 1 1 1

От латинского aequivalens - равноценное.

«… тогда и только тогда, когда … .»

EQV

~~

A  B, A ~ B

A ~ B

B

A

0 0 1 0 1 0 1 0 0 1 1 1

10

Задание 1 Расставь соответствующие числа

А → В

Логическое сложение

Наука о формах и способах мышления

Логическое отрицание

ИСТИНА и ЛОЖЬ

А ↔ В

&

Наука об операциях над высказываниями

Повествовательное предложение, в котором что-либо утверждается или отрицается

• Логика
• Высказывание
• Алгебра логики
• Логическая константа
• Дизъюнкция
• Инверсия
• Конъюнкция
• Импликация
• Эквивалентность

1.Операции в скобках 2.Отрицание ( над одной переменной ) 3.Логическое умножение 4.Логическое сложение 5.Логическое следование 6.Логическое равенство

Найдите значения логических выражений

1

F = (0 v 0) v (1 v 1)

F = ( 1 v 1 ) v (1 v 0 )

F = ( 0 & 0 ) & (1 & 0 )

F = ¬1 & (1 v 1) v ( ¬0 & 1)

F = ( ¬1 v 1) & (1 & ¬1) &(¬1 V 0)

1

0

1

0

Таблицы истинности

Логическое выражение – формула, в которую входят логические переменные и знаки логических операций.

Пример:

Для логического выражения можно построить таблицу истинности , которая определяет его истинность или ложность при всех возможных комбинациях исходных значений простых высказываний.

Построение таблицы истинности

• Определить количество строк в таблице по формуле 2 n , где n – количество логических переменных.
• Определить количество столбцов таблицы: количество логических переменных + количество логических операций.
• Построить таблицу истинности, обозначить столбцы, внести всевозможные наборы исходных данных логических переменных.
• Заполнить таблицу истинности, выполняя базовые логические операции в необходимой последовательности.

Построение таблицы истинности для

• Количество строк таблицы 2 2 = 4, т.к. в формуле две переменные A и B .
• Количество столбцов: 2 переменные + 5 логических операций = 7.

A

0

B

A v B

0

0

1

1

1

0

1

1

0

0

1

1

1

1

1

1

1

1

1

0

0

1

0

0

1

0

0

Равносильные логические выражения

Равносильные логические выражения - это выражения, у которых последние столбцы таблиц истинности совпадают, обозначают “=“ .

Докажите равносильность выражений:

Таблица истинности для

Таблица истинности для

A

0

B

A

AvB

0

0

B

0

0

1

0

1

1

1

0

1

1

1

0

1

Задание 2

Даны высказывания: А = { 2 · 2 = 4 } В = { 2 + 2 = 5 } Определите истинность высказываний:

• А
• ¬ В
• A & B
• B
• ¬A
• A v B

Задание 3

Заполните таблицу истинности для выражения: X v Y & ¬Z

X

Y

0

0

Z

0

0

0

0

¬Z

1

Y& ¬Z

1

1

0

0

XvY&¬Z

1

0

1

0

1

1

1

1

0

1

Задание 4

Заполните пустые ячейки таблицы истинности

A

B

0

¬B

AvB

1

1

0

¬( AvB)

0

1

¬B& ¬( AvB)

1

0

0

0

0

1

0

Задание 5

Укажите логическое выражение, соответствующее высказыванию: «В субботу я поеду на дачу и, если будет жарко, то я пойду купаться».

А = «Я поеду на дачу»

В = «Будет жарко»

С = «Я пойду купаться»

• F = A v (B → C)
• F = (A v B) → C
• F = (A & B) → C
• F = A & (B → C)

Закон ассоциативности

a&(b&c)=(a&b)&c=a&b&c

av(bvc)=(avb)vc=avbvc

Закон коммутативности

a&b=b&a

avb=bva

Закон двойного

отрицания

A=A

Закон дистрибутивности

a&(bvc)=a&b v a&c

avb&c=(avb)&(avc)

Закон де Моргана

a&b=avb

avb=a&b

Закон идемпотентности

ava=a

a&a=a

Свойство констант

av0=a a&0=0

av1=1 a&1=a

Закон

исключения

Третьего

ava=1

Закон

противоречия

a&a=0

Закон поглощения

Ava&b=a

A&(avb)=a

Закон склеивания

a&bva&b=a

a  b=avb

Закон без названия

ava&b=avb

a  b=a&bva&b