Краткое введение в исчисление высказываний

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

Обычно термин высказывание используется для логических переменных, принимающих одно из двух значений F и Т, которые представляют понятия «ложь» и «истина». На значениях типа «логический» определены пять операций: отрицание: (NOT b), конъюнкция: (b AND с), дизъюнкция: (b OR с), импликация: (b с), равенство: (b = с). Высказывания строятся по следующим правилам.

1.F и Т – высказывания.

2.Идентификаторы (непустая последовательность букв и цифр, начинающаяся с буквы) являются высказываниями.

3.Если b – высказывание, то (NOT b) высказывание.

4.Если b и с – высказывания, то (b OR с), (b AND с), (b = с), (b с) – также высказывания.

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

1.Значение Т есть Т, значение F есть F.

2.Значения (NOT b), (b AND с), (b OR с), (b с), (b = с), где b и с – константы F и Т в любой комбинации, определяются по таблице, называемой таблицей истинности.

b	c	NOT b	b AND с	b OR с	b с	b = с
F	F	T	F	F	T	T
F	T	T	F	T	T	F
T	F	F	F	T	F	F
T	T	F	T	T	T	T

3.Значение постоянного высказывания, содержащего более чем одну операцию, получается последовательным применением таблицы истинности к подвысказываниям этого высказывания и заменой подвысказываний на их значения до тех пор, пока высказывание не сведется к F или Т.

Состояние s – это функция из множества идентификаторов в множество значений F и Т. Высказывание E определено в состоянии s, если каждый идентификатор из E встречается в s. s(E) – значение E в состоянии s – получаемое заменой всех вхождений идентификаторов b в высказывание E на их значения s(b) и вычислением получившегося постоянного высказывания.

Тавтология – высказывание, истинное в любом состоянии, в котором оно определено.

Высказывание выражает, или описывает, множество состояний, в котором оно истинно.

Правила старшинства операций:

1.Последовательность одноименных операций вычисляется слева направо.

2.Порядок вычислений различных между собой и смежных в записи высказывания операций определяется списком: NOT,AND,OR, , =.

Вычисление высказываний редко бывает самоцелью. Чаще необходимо манипулировать ими, чтобы вывести «эквивалентные», но более простые высказывания.

Высказывания Е1 и Е2 эквивалентны, если и только если Е1 = Е2 есть тавтология. Здесь Е1 ~ Е2 эквивалентность.

1. Законы коммутативности: (Е1 Е2) = (Е2 Е1), - обозначает операции = , AND, OR.

2. Законы ассоциативности: (Е1 Е2) Е3 = Е1 (Е2 Е3), - обозначает операции AND, OR.

3. Законы дистрибутивности: (Е1 Е2) Å Е3 = (Е1 Å Е3) (Е2 Å Е3), и Å - обозначают операции AND, OR.

4. Законы де Моргана: NOT (Е1 Е2) = NOT Е1 Å NOT Е1), и Å- обозначают операции AND, OR.

5. Закон отрицания: NOT(NOTЕ1) = Е1.

6. Закон исключенного третьего: Е1 OR NOT Е1 = Т.

7. Закон противоречия: Е1 AND NOT Е1 = F.

8. Закон импликации: : (Е1 Е2) = NOT Е1 OR Е2.

9. Закон равенства: (Е1 = Е2) = (Е1 Е2) AND(Е2 Е1).

10.Законы упрощенияOR: Е1OR Е1 = Е1, Е1OR (Е1AND Е2) = Е1,Е1 OR Т = Т, Е1 OR F = Е1.

11.Законы упрощенияAND: Е1AND Е1 = Е1, Е1AND (Е1OR Е2) = Е1,Е1 AND Т = Е1, Е1 AND F = F.

12.Закон тождества Е1 = Е1.

Для вычисления высказываний используют правила подстановки и транзитивности.

Правило постановки: Если е1 = е2 – эквивалентность, а Е(х) – высказывание, записанное как функция от одного из своих идентификаторов х. Тогда Е(е1) = Е(е2) и Е(е2) = Е(е1) эквивалентности.

Правило транзитивности: Если е1 = е2 и е2 = е3 – эквивалентности, то е1 = е3 - эквивалентности.

Для формулирования развернутых высказываний используются кванторы.

Квантор существования ($i: m i < n: E_i).

Квантор всеобщности ("i: m i < n: E_i) = NOT($i: m i < n: NOTE_i)

Множество значений, удовлетворяющих m i < n, называется областью значений квантифицированной переменной i.

Вхождение идентификатора i в предикат называется связанным, если оно находится в области действия квантора "i или $i, и свободным в противном случае.

В одном и том же выражении один и тот же идентификатор не может быть как связанным, так и свободным и идентификатор не может быть связан двумя различными кванторами.

Не нашли, что искали? Воспользуйтесь поиском по сайту: