рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Алгоритм преобразования произвольной формулы в СНДФ.

Реферат Курсовая Конспект

Выберите учебное заведение

Алгоритм преобразования произвольной формулы в СНДФ.

Алгоритм преобразования произвольной формулы в СНДФ. - раздел Математика, КУРС ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ 1) Выразить Все Логические Операции Через Конъюнкцию, Дизъюнкцию И Отрицание....

1) Выразить все логические операции через конъюнкцию, дизъюнкцию и отрицание.

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

3) Если имеется несколько одинаковых элементарных конъюнкций, то оставляем только одну из них ().

4) Если в некоторую элементарную конъюнкцию входит переменная со своим отрицанием, то удаляем эту конъюнкцию (, а ).

5) Если в какую-то элементарную конъюнкцию не входит какая-либо переменная, то добавляем её дизъюнктивно, т. е. с помощью соотношений: , . Затем снова возвращаемся к пункту 2).

Аналогично можно составить алгоритм получения СНКФ. Для примера преобразуем к виду СНКФ уже рассмотренную формулу .

Имеем: = = = == == =.

Следует отметить, что в каждую скобку СНКФ и СНДФ должны входить все переменные (с отрицанием или без него), входящие в исходную формулу. СНДФ (СНКФ) можно рассматривать как частные случаи ДНФ (КНФ). ДНФ (дизъюнктивная нормальная форма) – это дизъюнкция элементарных конъюнкций (как и СНДФ). Отличие состоит в том, что для ДНФ в каждую элементарную конъюнкцию не обязательно входят все переменные. ДНФ может быть получена с помощью пунктов 1-4 алгоритма. Аналогично для КНФ. В отличие от совершенных форм, ДНФ (КНФ) могут быть не единственными.

Определение 5: Система логических операций называется полной, если всякую формулу алгебры логики можно представить только через операции данной системы.

Теорема: Система логических операций полна.

Доказательство. Выше было показано, что любую формулу алгебры логики можно представить в виде СНДФ или в виде СНКФ, где используются только конъюнкция, дизъюнкция и отрицание. Теорема доказана.

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

Все эти рассуждения можно продемонстрировать на примере:

= = = .

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

КУРС ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ... ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм преобразования произвольной формулы в СНДФ.

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ
(для студентов специальности “Прикладная математика”) У т в е р ж д е н о на заседании кафедры прикладной математики

Отрицание – обозначается ,читается:«не » или «неверно, что ».
2) Дизъюнкция (логическое сложение), обозначаемое(читается «

Упражнения для самостоятельной работы.
1. Даны следующие высказывания: P = «Данное число – целое», Q = «Данное число – положительное», R = «Данное число – простое», S = «Данное число

Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются формулы из некоторых

Доказательство.
Необходимость: Пусть формулы и

Упражнения для самостоятельной работы.
1. Определить, является ли данная последовательность символов формулой: 1)

Совершенные нормальные конъюнктивные и дизъюнктивные формы. Полные системы логических связок.
Определение 1:Элементарной конъюнкцией называется конъюнкция переменных, каждая из которых стоит под знаком отрицания или без него. Например:

Определение 4: Формула, представленная в виде конъюнкции элементарных дизъюнкций, называется совершенной нормальной конъюнктивной формой (СНКФ).
Замечание: Каждая элементарная конъюнкция (дизъюнкция), входящая в СНДФ (в СНКФ), должна содержать все пропозиционные буквы, входящие в исходную формулу. Только в этом случае м

Замечание о представлении произвольной формулы многочленом Жегалкина.
Введём следующие обозначения: , .

Упражнения для самостоятельной работы.
1. Привести к СНДФ данные формулы: 1) , 2)

Определения.
В математике принято одной и той же буквой обозначать различные объекты, т. е. под буквой фактически понимается переменная, принимающая значения из некоторого множества. Такие перем

Определение 3: Множество всех значений таких, что предикат при этих значениях принимает значение «истина», называется областью истинности предиката.
Определение 4: Предикат , определённый на множестве

Упражнения для самостоятельной работы.
1. Прочитать следующие высказывания. Какие из них принимают истинные значения? 1) ; 4)

Формулы и тавтологии логики предикатов.
При введении определения формул логики предикатов будем использовать следующие обозначения (алфавит): 1)

Упражнения для самостоятельной работы.
1. Записать следующие высказывания в виде формул логики предикатов. 1) Всякое натуральное число, делящееся на 12, делится на 2, 4 и

Некоторые схемы доказательства теорем.
Многие теоремы в математике имеют форму импликации . В этом случае условие

Рассмотрим некоторые схемы доказательства теорем.
1) Пусть и - одноместные предикаты,

Упражнения для самостоятельной работы.
1.Записать на языке логики предикатов аксиому математической индукции. 2. Записать на языке логики предикатов следующую те

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

Упражнения для самостоятельной работы.
1. Указать свободные и связные вхождения переменных в следующих формулах: 1)

Свойства теорий первого порядка.
Все результаты этого параграфа относятся к произвольной теории первого порядка. Всяк

Теоремы о полноте.
Теорема 1: Во всяком исчислении предикатов первого порядка всякая теорема является логически общезначимой. Доказательство:

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

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

Принцип двойственности.
Пусть – некоторое подмножество множества булевых функций:

Линейные функции. Монотонные функции.
Рассмотрим систему функций: ,

Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём сле

Упражнения для самостоятельной работы.
1) Сколько имеется различных двоичных наборов длины