Алгебра логики

1.

2.

• Высказывание
- это всякое повествовательное
предложение, утверждающее что-либо о чем-либо,
при этом непременно истинное или ложное.
• Логическими значениями высказываний являются
«истина» и «ложь», обозначаемые 1 и 0.
• Высказывания,
представляющие
собой
одно
утверждение,
называются
простыми
или
элементарными, высказывания, получающиеся из
элементарных с помощью грамматических связок
«не», «и», «или», «если…то…» называются
сложными.
• Высказывание обозначается символами A, B, C…X,
Y, Z …

3.

Пример:
А – «Этот четырехугольник
параллелограмм»,
В – «Этот четырехугольник ромб»
А и В - простые высказывания.
Образуем сложные высказывания.
«Этот четырехугольник есть параллелограмм
и ромб»
А В

4.

1. Отрицанием
высказывания х называется
новое
высказывание,
которое
является
истинным, если высказывание х ложно, и
ложным , если х –истинно. Обозначается х,
или х´
х
х
1
0
0
1

5.

2. Логическое умножение (конъюнкция).
Конъюнкцией двух высказываний х и у
называется новое высказывание z, которое
истинно, только когда оба высказывания х и у
истинны, и ложно, когда хотя бы одно из них
ложно.
х
у
х у
1
1
1
1
0
0
0
1
0
0
0
0

6.

3. Логическое сложение (дизъюнкция).
Дизъюнкцией двух высказываний х и у
называется новое высказывание, которое
считается истинным, если хотя бы одно из
высказывания х и у истинно, и ложным, если они
оба ложны.
х
у
х у
1
1
1
1
0
1
0
1
1
0
0
0

7.

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

8.

5. Эквиваленция (логическая эквивалентность).
Эквиваленцией двух высказываний х и у
называется новое высказывание, которое истинно,
когда оба высказывания х и у либо одновременно
истинно, либо одновременно ложно, и ложно во
всех остальных случаях.
х
у
х у
1
1
1
1
0
0
0
1
0
0
0
1

9.

Формулой логики высказываний называется
1) любая отдельно стоящая буква A, B, C, …, X
2) Если А, В – формулы, то А´, А۸В, А۷В, А→В,
А↔В – формулы,
3) Других формул нет.
Всякое сложное высказывание, которое может
быть получено из элементарных высказываний с
помощью логических связок, называется
формулой алгебры логики.

10.

Формула
А называется тождественно
истинной или тавтологией, если она
принимает значение 1 при всех значениях
входящих в нее переменных.
Формула
А называется тождественно
ложной или противоречием, если она равна
0 при всех значениях входящих в нее
переменных.
Формула А называется выполнимой, если
существуют такие логические значения
переменных, при которых эта формула
принимает значение «истина».

11.

А
В
А
В
А В
В А
Ф
1
1
0
0
1
0
0
1
0
0
1
0
1
1
0
1
1
0
1
0
0
0
0
1
1
1
0
0

12.

Ф(p,q)=p۸q→(p→q)
p
q
p۸q
p→q
ф
и
и
и
и
и
и
л
л
л
и
л
и
и
и
и
л
л
и
и
и

13.

Формулы
Ф( р1 , р2 , … , р