Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Дисциплины:
2017-10-21 | 514 |
5.00
из
|
Заказать работу |
|
|
Конъюнкция дизъюнкция отрицание импликация эквиваленция
Опр. Конъюнкция высказываний 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 существует равносильная формула, имеющая КНФ.
|
|
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!