Математическая логика

Конъюнкция

Логическое умножение

Определение — Конъюнкцией высказываний A B называется высказывание C, являющиеся истинным, когда A B оба истинные и ложным в остальных случаях

C=A^B

Или C=A*B

Или C=A&B

A	B	A&B
1	0	0
0	1	0
1	1	1
0	0	0

Дизъюнкция

Дизъюнкцией высказывания A B называется высказывание C, которое ложно при ложности A B

И истинное во всех других случаях

C=A+B

C=AVB

A	B	AVB
1	0	1
0	1	1
1	1	1
0	0	0

Строгая дизъюнкция

Строгой дизъю. Высказывания A B называется высказывание C истинное лишь в случае, когда логический смысл A B противоположен и ложная в других случаях

С=A плюс в окружности B (либо a либо b )

A	B	A+b
1	0	1
0	1	1
1	1	0
0	0	0

Импликация.

Импликацией A B называется высказ C ложное только тогда, когда A-истинна B-ложь

Истинно во всех других случаях

С=A>B если а то b

A	B	a>b
1	0	0
0	1	1
1	1	1
0	0	1

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

Эквиваленцией высказываний наз выз. Истинное в случае когда А и В одинаковые. И ложное в остальных

С=A~B

A	B	A~B
1	0	0
0	1	0
1	1	1
0	0	1

Эквиваленция — необходимо и достаточно.

А тогда и только тогда когда В

/ ^ V плюс в круге > ~

Свойства логических операций

1) AVB=BVA – коммутативность дизъюнкции

2) A^B=B^A-коммутативность конъюнкции

3) AV(BVC)=(AVB)VC

4) A&(B&C)=(A&B)&C –сочетательные законы

5) A&(B|C)=A&B|C&C – дистрибутивный закон для конъюнкции и дизъюнкции

6) A|(B&C)=(A|B)&(A|C)

Пример:

Допустим, что А=0 В=1 С=1

Вычислим левую и правую часть тождества 6

0|(1&1)=1

(0|1)&(0|1)=1

7) Свойства логических констант

A&1=A

A&0=0

A|0=A

A|1=A

Законы Де Моргана

не A^B= не a v не b

А	В	A^b
1	0	0	1
0	1	0	1
1	1	1	0
0	0	0	1

Не a v b = не a ^ не B

Закон исключения третьего

A v не a =1

Закон противоречия

A^-A=0

Закон снятия двойного отрицания

—a=a

Чётное количество отрицания снимается

Нечётное — остаётся одно

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

A^(AVB)=A

AV(A^B)=A

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

AVA=A

A^A=A

A^(a v 1)=a

Пример:

Упростить выражение

(-aVb)V((C(+)d)^(BV-a))=-AVB

Лекция №2

Формулы логики высказываний

Понятие формулы логики высказываний и её логический смысл

Вычисление значений истинности формул логики высказываний

Тождественно истинные и тождественно ложные формулы логики высказываний

Логическая равносильность формул.

Определение формулы логики высказываний

1. Всякая переменная или логическая константа – есть формула логики высказываний

2. Если А В формулу логики высказываний, то следующие последовательности символов тоже являются формулами логики высказываний.

-A, AVB , A^B, A>B, A~B, A(+)B