Элементы математической логики. Формулы алгебры логики

1.

2. Логика высказываний

I.
II.
III.
IV.
V.
VI.
VII.
VIII.
IX.
Высказывания
Истинность высказывания
Операции над высказываниями
Дизъюнкция
Конъюнкция
Импликация
Эквиваленция
Штрих Шеффера
Штрих Лукасевича

3. КОНЪЮНКЦИЯ: бинарное

• Обозначается:
^
(логическое умножение,
операция «и»)
x
y
0
0
0
1
0
1
0
0
1
1
1
X
^
0
Y

4. ТАБЛИЦЫ ИСТИННОСТИ. СВОЙСТВА ОТРИЦАНИЕ: унарное

Высказывание это: любое
предложение, утверждающее чтолибо, при этом всегда можно сказать
истинно оно или ложно, в данном
месте в данное время.
1-истина (и, true).
0-ложь (, false).
Высказывание, получаемое из
элементарных с помощью связок: не,
и, или, если то, тогда и только тогда называются сложными или
составными. Ни одно высказывание
не может быть одновременно
истинным или ложным.
• Пример:
=
x = x (враг моего врага мой друг)
=
Двойное отрицание - x
X
_
X
0
1
1
0

5. ДИЗЪЮНКЦИЯ

• Обозначается: V
• (логическое
сложение, операция
«или»)
X
y
XVY
0
0
0
0
1
1
1
0
1
1
1
1

6. ИМПЛИКАЦИЯ

• Обозначается: X Y
• (Импликация двух
высказываний x и y
которое ложно, если
x-истина, а y-ложно,
и истина во всех
остальных случаях)
X
y
X Y
0
0
1
0
1
1
1
0
0
1
1
1

7. Эквиваленция

• Обозначается: X ↔ Y
• (Эквиваленция двух
высказываний x и y,это
новое высказывание,
это истина когда оба
высказывания
одновременно истина и
одновременно ложь, и
ложь в остальных
других случаях)
X
y
X ↔Y
0
0
1
1
0
0
0
1
0
1
1
1

8. Штрих Шеффера:

• Обозначается: X /Y
• (высказывание, которое
ложно только тогда,
когда оба высказывания
истина)
X
y
X /Y
0
0
1
0
1
1
1
0
1
1
1
0

9. Штрих Лукасевича

• Обозначение:X ↓Y
• (высказывание,
которое истина в
одном случае, когда
оба высказывания
ложно)
X
y
X ↓Y
0
0
1
0
1
0
1
0
0
1
1
0

10.

11. Равносильные формулы

• Две формулы А и В
равносильны, если они
принимают одинаковые
логические значения на
любом наборе входящих
формулы элементарных
высказываний.
1. А≡В
=
3. x x y y
2. x≡x
• А называется тождественно
ложной, если принимает
значение нуля, при всех
значениях входящих в неё
переменных.
• А называется тождественно
истинным высказыванием,
если она принимает
значение единицы при
любом значении входящих
переменных.

12. Основные равносильности алгебры логики

1. x x x
2. x x x
3. x 1 x
4. x 1 1
5. x 0 0
6. x 0 x
7. x x 0 закон противоречия
8. x x 1 закон исключенного третьего
9. x x закон снятия двойного отрицания
10.а) x ( y x) x
законы поглощения
в) x ( y x) x

13. Равносильности выражающие одни логические функции через другие

1.
2.
3.
4.
5.
6.
x y ( x y ) ( y x)
x y x y
x y x y
x y x y
x y x y
x y x y

14. Равносильности выражающие основные законы алгебры логики

1. x y y x
законы коммутативности
2. x y y x
3.
4.
5.
6.
x ( y z ) ( x y ) z закон ассоциативности конъюнкции
x ( y z ) ( x y ) z закон ассоциативности дизъюнкции
x ( y z) ( x y) ( x z)
x ( y z) ( x y) ( x z )
Итак, алгебра-логика обладает коммутативными и
ассоциативными законами относительно операции
конъюнкции и дизъюнкции и дистрибутивным
законом конъюнкции относительно дизъюнкции.