Конъюнкция дизъюнкция отрицание импликация эквиваленция

Конъюнкция дизъюнкция отрицание импликация эквиваленция

Опр. Конъюнкция высказываний X и Y - высказывание, полученное при помощи союза «и», т.е. «… X… и … Y …».

X & Y

Опр. Дизъюнкция высказываний X и Y - высказывание, полученное при помощи союза «или», т.е. «… X… или … Y …».

X Ú Y

Опр. Конъюнкция высказываний X и Y - высказывание, полученное при помощи союза «и», т.е. «… X… и … Y …».

X & Y

Опр. Дизъюнкция высказываний X и Y - высказывание, полученное при помощи союза «или», т.е. «… X… или … Y …».

X Ú Y

Опр. Отрицание высказывания X - высказывание, полученное при помощи приставки «не», т.е. «не … X…».

Ø X

Опр. Импликация высказываний X и Y - высказывание, полученное при помощи конструкции «Если … X…, то … Y …».

X ® Y

Опр. Импликация высказываний X и Y - высказывание, полученное при помощи конструкции «Если … X…, то … Y …».

X ® Y

Опр. Эквиваленция высказываний X и Y - высказывание, полученное при помощи конструкции «… X…, если и только если … Y …».

X «Y

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

Атомарная формула логики высказываний - заглавная буква латинского алфавита, с индексом или без, а также символ 0 или 1.

 

Опр. Формула логики высказываний - выражение одного из двух видов:

1) атомарная формула;

2) (F & G), (F Ú G), (Ø F), (F ® G), (F «G),

где F и G - формулы логики высказываний.

 

Для уменьшения количества скобок договоримся о приоритетах операций:

Ø		наивысший
&	Ú	средний
®	«	низший

Примеры:

1. Формула Ø X & Y ® Z означает ((Ø X) & Y) ® Z.

2. Выражение X & Y Ú Z не является формулой.

4. Логическое следствие

Опр. Формула G называется логическим следствием формул, если для любой интерпретации из того, что все значения истинны, следует, что значение истинно.

Замечание. Формула G является логическим следствием формул , если .

Опр. Множество формул выполнимо, если существует интерпретация такая, что все значения истинны.

Невыполнимо - в противном случае.

Теорема.

Формула G является логическим следствием формул Û множество формул не выполнимо.

 

 

5. Нормальные формы.

Опр. Литерал - атомарная формула (кроме 0 и 1), или ее отрицание.

Элементарная конъюнкция - литерал или конъюнкция литералов.

Опр. Формула F имеет дизъюнктивно-нормальную форму (ДНФ), если она является элементарной конъюнкцией или дизъюнкцией элементарных конъюнкций.

(…. & …. & …) Ú (…. & ….) Ú (…) …

Теорема.

Для всякой формулы F существует равносильная формула, имеющая ДНФ.

Доказательство:

Алгоритм приведения к ДНФ.

1. Исключить эквиваленцию и импликацию (по законам 21 и 20).

2. Занести отрицание к атомарным формулам (по законам де Моргана 17 и 18).

3. К не элементарным конъюнкциям применить законы дистрибутивности (11 и 12).

Опр. Формула F имеет совершенную дизъюнктивно-нормальную форму (СДНФ) относительно атомарных формул , если:

1) в записи F участвуют только ;

2) F имеет ДНФ, т.е. ;

3) Каждая содержит или , или , для любого j.

4) F не содержит одинаковых элементарных конъюнкций.

Теорема.

Для всякой выполнимой формулы F существует равносильная формула, имеющая СДНФ.

Доказательство:

Алгоритм приведения к СДНФ.

Алгоритм приведения к СДНФ.

1, 2, 3 - из алгоритма приведения к ДНФ.

Результат - формула , равносильная исходной. 4. Если не содержит ни , ни , то заменяем на .

5. Если F содержит несколько одинаковых элементарных конъюнкций, то вычеркиваем их все, кроме одной.

Элементарная дизъюнкция - литерал или дизъюнкция литералов.

Опр. Формула F имеет конъюнктивно-нормальную форму (КНФ), если она является элементарной дизъюнкцией или конъюнкцией элементарных дизъюнкций.

(…. Ú …. Ú …) & (…. Ú ….) & (…) …

Теорема.

Для всякой формулы F существует равносильная формула, имеющая КНФ.

 

 

Теорема.

Множество дизъюнктов S невыполнимо Û из S выводится пустой дизъюнкт.

Схема применения метода резолюций.

Дано: .

1. Формулы приводятся к КНФ.

2. Все получившиеся дизъюнкты собирают в множество S.

3. Строится вывод □ из S.

 

Теорема.

Û

Законы логики предикатов:

1) - 21) аналогичны законам логики высказываний.

22) ;

23) ;

Замечание:

1. .

Для доказательства неравносильности можно привести контрпример.

Пусть = «Число x чётное», = «Число x нёчетное» - одноместные предикаты на N.

Тогда и левая часть и правая часть равенства являются высказываниями:

л.ч. = «Для любого натурального числа x выполняется, что x чётное или x нечётное» = 1;

п.ч. = «Любое натуральное число чётное или любое натуральное число нечётное» = 0 Ú 0 = 0.

2. ;

Доказательством служит такая же интерпретация, как в предыдущем случае.л.ч. = «Существует натуральное число x, такое, что выполняется x чётное и x нечётное» = 0;

п.ч. = «Существует натуральное число чётное и существует натуральное число нечётное» = 1 & 1 = 1.

24) ;

25) ;

Замечание:

Для доказательства неравносильности можно привести контрпример.

Пусть = «x £ y» - двухместный предикат на N.

л.ч. = «Для любого числа x существует y, превышающий или равный x» = 1.

п.ч. = «Существует число y, такое, что для любого x выполняется x £ y» = 0.

26) ;

27) ;

28) ;

29) ;

Пусть , не содержит y, не содержит x.

30) ;

31) ;

32) ;

33) .

Опр. Формула называется логическим следствием формул , если для любой интерпретации на множестве M, и любых элементов , из того, что все значения , …, истинны, следует, что значение истинно.

9. Нормальные формы в логике предикатов

Опр. Формула F имеет предварённую нормальную форму (ПНФ), если , где , H не содержит кванторов.

Теорема.

Для всякой формулы F существует равносильная формула, имеющая ПНФ.

Доказательство:

Алгоритм приведения к ПНФ.

1. Исключить эквиваленцию и импликацию (по законам 21 и 20).

2. Занести отрицание к атомарным формулам (по законам де Моргана 17 и 18).

3. Вынести кванторы вперед, используя (если нужно) переименование переменных (по законам 22, 23, 28 - 33).

Опр. Формула F имеет сколемовскую нормальную форму (СНФ), если , где H не содержит кванторов и имеет КНФ.

Теорема.

Для всякой формулы F существует формула, имеющая СНФ, одновременно с F выполнимая или невыполнимая. Доказательство:

Алгоритм приведения к СНФ.

1, 2, 3 - из алгоритма приведения к ПНФ.

Результат .

4. Бескванторную часть H привести к КНФ.

5. Исключить кванторы существования, поочередно слева направо, применяя одно из двух правил:

1 случай) ~ , где a - символ константы.

2 случай) ~

~ , где - символ функции, зависящей от переменных .

При выполнении 1, 2, 3, 4 шагов алгоритма получается формула, равносильная F, следовательно, выполнимая или не выполнимая одновременно с F.

Если существует интерпретация j, при которой формула истинна, то существует значение , такое, что при этой же интерпретации j значение истинно. Т.е. формула выполнима.

Если существует интерпретация j, при которой формула истинна, то для любых значений переменных существует подходящее значение , такое, что при этой же интерпретации j значение истинно. Т.е. существует функция (), для которой формула выполнима.

Опр. Множество формул выполнимо, если существует интерпретация на множестве M, и существуют элементы , такие, что все значения , …, истинны.

Невыполнимо - в противном случае.

Теорема.

Формула G является логическим следствием формул Û множество формул не выполнимо.

10. Метод резолюций в логике предикатов

Опр. Подстановкой называется множество равенств , где , - терм, не содержащий .

Обозначение: - формула, полученная из F подстановкой s.

Опр. Правило резолюций в логике предикатов - из дизъюнктов и выводится дизъюнкт , где подстановка s такая, что и совпадают.

«Наиболее общий унификатор».

Опр. Пусть S множество дизъюнктов. Будем говорить, что дизъюнкт выводится из S, если существует последовательность дизъюнктов , такая, что каждый принадлежит S,или получен по правилу резолюций из дизъюнктов , или получен подстановкой s.

Вывод из S - эта последовательность .

Теорема.

Множество дизъюнктов S логики предикатов невыполнимо Û из S выводится пустой дизъюнкт.

Схема применения метода резолюций.

Дано: .

1. Формулы привести к СНФ.

2. Отбросить кванторы общности.

3. Все получившиеся дизъюнкты собрать в множество S.

4. Построить вывод □ из S.

Языки и операции с ними

Опр. Алфавит S - конечное непустое множество.

Буква - каждый элемент множества S.

Слово над алфавитом S - конечная последовательность , где каждая .

(цепочка, string)

Длина слова - количество n символов в слове.

Пустое слово e - слово длины 0.

Обозначение - множество всех слов (включая пустое) над алфавитом S.

Опр. (Умножение слов)

Произведением слова на слово называется слово .

(конкатенация)

Свойства:

1) умножение не коммутативно: ;

2) умножение ассоциативно: ;

3) пустое слово e является нейтральным элементом относительно умножения: .

Следствие: - полугруппа с нейтральным элементом (моноид).

Опр. Степенью k слова u называется .

Опр. Языком над алфавитом S называется .

Пустым языком называется .

Пример.

1) Естественный (русский) язык.

2) Язык формул математической логики.

3) S ={0, 1}; язык компьютерных программ, записанных на автокоде.

Операции над языками:

пересечение ; объединение ;

дополнение (универсальным множеством является ).

Опр. Множество - набор каких-то объектов.

Элемент множества - каждый объект.

Множество содержит элемент: .

Опр. Пересечение множеств A и B - множество, состоящее из всех элементов, принадлежащих A и B одновременно.

A Ç B

Опр. Объединение множеств A и B - множество, состоящее из всех элементов, принадлежащих или A, или B, или A и B одновременно (принадлежащих A или B).

A È B

Опр. Универсальное множество для системы множеств - множество, содержащее все элементы этих множеств.

I

Опр. Дополнение к множеству A - множество, состоящее из всех элементов универсального множества, не принадлежащих A.

Опр. Произведением языков и называется язык

.

Опр. Степенью k языка L называется

Обозначим .

Опр. Итерацией языка L называется язык

Приоритеты операций:

итерация	наивысший
умножение	высокий
дополнение	средний
пересечение, объединение	низший

Свойства операций:

1), 2) Идемпотентность

A Ç A = A;

A È A = A.

Замечание: ; .

3), 4) Коммутативность

A Ç B = B Ç A;

A È B = B È A.

5), 6) Ассоциативность

(A Ç B)Ç C= A Ç (B Ç C);

(A È B)È C= A È (B È C).

7), 8) Дистрибутивность

A Ç (B È C) = (A Ç B)È (A Ç C);

a × (b + c) = (a × b) + (a × c)

A È (B Ç C) = (A È B)Ç (A È C).

9), 10) Законы поглощения

A Ç (A È B) = A;

A È (A Ç B) = A.

11), 12)

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

закон «исключенного третьего».

13), 14) Законы де Моргана

;

.

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

.

20) ;

;

21) ; ;

22) ;

23) .

Теорема.

Класс замкнут относительно операций пересечения, объединения, дополнения, произведения, итерации.

Теорема.

Класс замкнут относительно операций пересечения, объединения, дополнения, произведения, итерации.

Доказательство:

Пусть - язык, допускаемый ДКА , - язык, допускаемый ДКА , и . Очевидно, , .

1. Покажем, что .

Построим НДА , где ,

.

, для ; .

.

По теореме из §4, существует ДКА, допускающий тот же язык.

2. Покажем, что .

Построим ДКА .

Рассмотрев любое слово w автомат переходит в какое-нибудь состояние q.

Если , т.е. , то , т.е. не является заключительным в автомате В.

И наоборот, если , т.е. , то ,

т.е. является заключительным в автомате В.

Следовательно, .

3. .

4. Покажем, что .

1 случай) , т.е. .

Построим НДА , где ,

;

, для ;

, для ; , для .

.

По теореме из §4, существует ДКА, допускающий тот же язык.

2 случай) , т.е. .

К автомату B из случая 1 добавим

.

По теореме из §4, существует ДКА, допускающий тот же язык.

5. Покажем, что .

Построим НДА , где ,

;

, для ;

, для .

По теореме из §4, существует ДКА, допускающий тот же язык.

Следствие.

Любой конечный язык допускается конечным автоматом.

Доказательство:

Конечный язык - конечное множество слов конечной длины.

1.Если язык пустой (т.е. пустое множество), то он допускается любым ДКА с пустым множеством заключительных состояний.

2. Если язык состоит из одного пустого слова, то он допускается

ДКА , где

, .

2. Если язык состоит из одного не пустого слова , то он допускается НДА , где

, …, .

По теореме из §4, существует ДКА, допускающий тот же язык.

4. Если язык , то .

Каждый язык допускается ДКА.

Объединение языков допускается автоматом, упоминавшимся в доказательстве теоремы о замкнутости.

Опр. Язык называется регулярным, если он получается из конечных языков применением операций объединения, произведения, итерации.

Обозначим класс всех регулярных языков над фиксированным алфавитом S.

Теорема (Клини).

= .

Замечание:

Для описания регулярного языка используется регулярное выражение без фигурных скобок.

Например. Для используется или .

 

 

Теорема.

Класс всех языков над алфавитом S, порождаемых праволинейной (или леволинейной) грамматикой, совпадает с классом языков, допускаемых конечным автоматом.

Применение КС-грамматики.

Транслятор º компилятор.

Компилятор - программа, переводящая текст программы, написанной на языке высокого уровня, в текст программы на автокоде (язык машинных команд) или Ассемблере.

Синтаксический блок - одна из главных частей компилятора, проверяет синтаксическую правильность программы (т.е. существование правильного перевода в автокод).

Пусть синтаксически правильные программы - слова некоторого языка. Тогда синтаксический блок проверяет, принадлежит ли входное слово языку правильных программ.

 

 

конъюнкция дизъюнкция отрицание импликация эквиваленция

Опр. Конъюнкция высказываний X и Y - высказывание, полученное при помощи союза «и», т.е. «… X… и … Y …».

X & Y

Опр. Дизъюнкция высказываний X и Y - высказывание, полученное при помощи союза «или», т.е. «… X… или … Y …».

X Ú Y

Опр. Конъюнкция высказываний X и Y - высказывание, полученное при помощи союза «и», т.е. «… X… и … Y …».

X & Y

Опр. Дизъюнкция высказываний X и Y - высказывание, полученное при помощи союза «или», т.е. «… X… или … Y …».

X Ú Y

Опр. Отрицание высказывания X - высказывание, полученное при помощи приставки «не», т.е. «не … X…».

Ø X

Опр. Импликация высказываний X и Y - высказывание, полученное при помощи конструкции «Если … X…, то … Y …».

X ® Y

Опр. Импликация высказываний X и Y - высказывание, полученное при помощи конструкции «Если … X…, то … Y …».

X ® Y

Опр. Эквиваленция высказываний X и Y - высказывание, полученное при помощи конструкции «… X…, если и только если … Y …».

X «Y

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

Атомарная формула логики высказываний - заглавная буква латинского алфавита, с индексом или без, а также символ 0 или 1.

 

Опр. Формула логики высказываний - выражение одного из двух видов:

1) атомарная формула;

2) (F & G), (F Ú G), (Ø F), (F ® G), (F «G),

где F и G - формулы логики высказываний.

 

Для уменьшения количества скобок договоримся о приоритетах операций:

Ø		наивысший
&	Ú	средний
®	«	низший

Примеры:

1. Формула Ø X & Y ® Z означает ((Ø X) & Y) ® Z.

2. Выражение X & Y Ú Z не является формулой.

4. Логическое следствие

Опр. Формула G называется логическим следствием формул, если для любой интерпретации из того, что все значения истинны, следует, что значение истинно.

Замечание. Формула G является логическим следствием формул , если .

Опр. Множество формул выполнимо, если существует интерпретация такая, что все значения истинны.

Невыполнимо - в противном случае.

Теорема.

Формула G является логическим следствием формул Û множество формул не выполнимо.

 

 

5. Нормальные формы.

Опр. Литерал - атомарная формула (кроме 0 и 1), или ее отрицание.

Элементарная конъюнкция - литерал или конъюнкция литералов.

Опр. Формула F имеет дизъюнктивно-нормальную форму (ДНФ), если она является элементарной конъюнкцией или дизъюнкцией элементарных конъюнкций.

(…. & …. & …) Ú (…. & ….) Ú (…) …

Теорема.

Для всякой формулы F существует равносильная формула, имеющая ДНФ.

Доказательство:

Алгоритм приведения к ДНФ.

1. Исключить эквиваленцию и импликацию (по законам 21 и 20).

2. Занести отрицание к атомарным формулам (по законам де Моргана 17 и 18).

3. К не элементарным конъюнкциям применить законы дистрибутивности (11 и 12).

Опр. Формула F имеет совершенную дизъюнктивно-нормальную форму (СДНФ) относительно атомарных формул , если:

1) в записи F участвуют только ;

2) F имеет ДНФ, т.е. ;

3) Каждая содержит или , или , для любого j.

4) F не содержит одинаковых элементарных конъюнкций.

Теорема.

Для всякой выполнимой формулы F существует равносильная формула, имеющая СДНФ.

Доказательство:

Алгоритм приведения к СДНФ.

Алгоритм приведения к СДНФ.

1, 2, 3 - из алгоритма приведения к ДНФ.

Результат - формула , равносильная исходной. 4. Если не содержит ни , ни , то заменяем на .

5. Если F содержит несколько одинаковых элементарных конъюнкций, то вычеркиваем их все, кроме одной.

Элементарная дизъюнкция - литерал или дизъюнкция литералов.

Опр. Формула F имеет конъюнктивно-нормальную форму (КНФ), если она является элементарной дизъюнкцией или конъюнкцией элементарных дизъюнкций.

(…. Ú …. Ú …) & (…. Ú ….) & (…) …

Теорема.

Для всякой формулы F существует равносильная формула, имеющая КНФ.