Конъюнкция дизъюнкция отрицание импликация эквиваленция
Конъюнкция дизъюнкция отрицание импликация эквиваленция
Опр. Конъюнкция высказываний 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 существует равносильная формула, имеющая КНФ.