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

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

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

Определение 4: Формула, представленная в виде конъюнкции элементарных дизъюнкций, называется совершенной нормальной конъюнктивной формой (СНКФ). - раздел Математика, КУРС ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ Замечание: Каждая Элементарная Конъюнкция (Дизъюнкция), ...

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

СНДФ и СНКФ можно составлять для данной формулы, пользуясь её таблицей истинности.

Рассмотрим таблицу истинности для произвольной формулы алгебры высказываний :

 

...
... ... ... ... ...
и л ... и и
... ... ... ... ...

 

Для каждой строки таблицы истинности строим элементарную конъюнкцию , которая истинна только для этой строки, а для всех остальных строк эта элементарная конъюнкция ложна. Пропозиционная переменная входит в элементарную конъюнкцию без черты, если в данной строке принимает значение «истина». Если же переменная принимает в данной строке значение «ложь», то в элементарную конъюнкцию эта буква входит с чертой.

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

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

Например, составим СНДФ для формулы .

 

и и и л и и
и и л л и л
и л и л л и
л и и и и и
и л л л л и
л и л и и л
л л и и и и
л л л и и л

 

СНДФ для данной формулы имеет вид: =

.

В правой части равносильности просто «перечислены» все строки таблицы истинности, в которых наша формула принимает значение «истина».

Из рассмотренного примера видно, что СНДФ существует для всякой выполнимой формулы.

Аналогичные рассуждения можно привести и для СНКФ.

Если произвольная формула не является тождественно истинной, то по таблице истинности для каждой строки, где наша формула ложна, строим элементарную дизъюнкцию, которая принимает значение «ложь» только в данной строке, а в остальных строках принимает значение «истина». Если пропозиционная буква в данной строке принимает значение «ложь», то она входит в элементарную дизъюнкцию без черты. Если же переменная в данной строке принимает значение «истина», то в элементарную дизъюнкцию она входит с чертой. Если построить такие дизъюнкции для всех строк таблицы, в которых формула принимает значение «ложь», и соединить их знаками конъюнкции, то полученная конъюнкция таких элементарных дизъюнкций имеет такую же таблицу истинности, что и исходная формула. Полученное представление формулы называется совершенной нормальной конъюнктивной формой (СНКФ).

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

Если же формула является тавтологией, то её можно представить в виде дизъюнкции .

Для рассмотренного примера СНКФ имеет вид:

.

Искать СНДФ или СНКФ по таблице не всегда удобно. Особенно для тех формул, которые зависят от 4-х и более переменных. Поэтому рассмотрим алгоритм, позволяющий преобразовать произвольную формулу в СНДФ или СНКФ.

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги