27. Высказывания.

Высказывания – это повествовательное выражение, которое либо истинно, либо ложно.

A, B, C….A1,A2,A3

A1: Киев – столица Украины (ист.)

А2: Снег – белый (ист.)

Логические операции над высказываниями

Отрицание высказывания P – называется новое высказывание, обозначаемое P, которое истинно, если высказывание Р ложно и наборот.

P P

1 0

0 1

Коньюнкция двух высказываний P и Q называется новое высказывание, обозначаемое PQ, которое истинно лишь в единственном случае, если высказывания Р и Q - истинны.

P Q PQ

0 0 0

0 1 0

1 0 0

1 1 1

Дизъюнкцией двух высказываний называется новое высказывание, обозначаемое РQ, которое истинно лишь в тех случаях, если хотя бы одно из высказываний истинно.

P Q PQ

0 0 0

0 1 1

1 0 1

1 1 1

Импликация двух высказываний Р и Q называется новое высказывание, обозначаемое РQ, которое ложно в единственном случае, когда Р – истинно, а другое высказывание – ложно. Р – посылка, Q - следствие

P Q PQ

0 0 1

0 1 1

1 0 0

1 1 1

Эквивалентность двух высказываний, обозначаемая РQ, которое истинно, когда P и Q одновременно либо истинны, либо ложны.

P Q РQ

0 0 1

0 1 1

1 0 0

1 1 1

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

Введем язык логики (алгебры) высказываний:

1. пропозициональные переменные (А, В, С..)

2. символы логичекских операций , , , ,

3. вспомогательные символы () ,

Индуктивное определение формулы алгебры высказываний:

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

2. если F1, F2 – формулы алгебры высказываний, то (F1), (F1F2), (F1F2), (F1F2),(F1F2) тоже формулы

3. никаких других формул нет

Пример:

А – 100 кратно 5

В – 100 кратно 2

С – 100 кратно 10

(АВ)С

28.Интерпретация формулы. Теорема.

Формализация – переход от высказываний естественного языка к формулам алгебры высказываний.

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

Классификация формул алгебры высказываний:

1. выполнимые

2. тождественно – истинные (тавтологии)

3. тождественно – ложные (противоречия)

F(X1, X2…)

Формула алгебры высказываний называется выполнимой, если существует такие конкретные высказывания А1…Аn, которые, будучи подставленными в эту формулу вместо переменных высказываний X1,…Xn соответственно, превращает её в истинное высказывание. Формула алгебры высказываний называется тавтологией, если она превращается в истинное высказывание при всякой подстановке вместо переменных X1,…Xn высказываний А1…Аn. Формула называется противоречием, если она превращается в ложное высказывание при всякой подстановке вместо X1,…Xn высказываний А1…Аn. Формулы F(X1, X2…) и H(X1, X2…) называются равносильными (эквивалентными), если при любых значениях входящих в них пропозициональных переменных они принимают одинаковые логические значения.

Теорема (признак равносильности формул). Две формулы F and H алгебры высказываний равносильны тогда, когда FH является тавтологией.

Лемма (о замене). Если в формуле некоторую её подформулу заменить на равносильную ей, то полученная формула будет равносильна исходной.