Алгебра логики высказываний Основные понятия

Скачать 428.51 Kb.

Название	Алгебра логики высказываний Основные понятия
страница	4/8
Дата публикации	02.12.2014
Размер	428.51 Kb.
Тип	Документы

100-bal.ru > Математика > Документы

1 2 3 4 5 6 7 8

Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма

Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний.

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

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

Например, для формулы А = х  (х  y) имеем:

А = х  ( х  y) = (х   х)  (х  y) = х  y, то есть

ДНФ А = (х   х)  (х  y) и

ДНФ А = х  y.

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

Как уже указывалось, СДНФ А может быть получена с помощью таблицы истинности.

Другой способ получения СДНФ формулы А основан на равносильных преобразованиях формулы и состоит в следующем:

путем равносильных преобразований формулы А получают одну из ДНФ А.
если в полученной ДНФ А входящая в нее элементарная конъюнкция В не содержит переменную x_i, то, используя закон B  (x_i   x_i) = B, элементарную конъюнкцию B заменяют на две элементарных конъюнкции (B  x_i) и (B   x_i), каждая из которых содержит переменную x_i.
если в ДНФ А входят две одинаковых элементарных конъюнкции В, то лишнюю можно отбросить, пользуясь равносильностью В  В = В.
если некоторая элементарная конъюнкция В, входящая в ДНФ А, содержит переменную x_i и ее отрицание  x_i, то, на основании закона x_i   x_i = 0, В = 0 и В, таким образом, можно исключить из ДНФ А, как нулевой член дизъюнкции.
если некоторая элементарная конъюнкция, входящая в ДНФ А, содержит переменную x_i дважды, то одну переменную можно отбросить, пользуясь законом x_i  x_i = x_i.

Ясно, что после выполнения описанной процедуры будет получена СДНФ А. Например, для формулы А = x  y  (x   y) ДНФ А = x  (x  y)  (y   y). Так как элементарная конъюнкция В = х, входящая в ДНФ А, не содержит переменной у, то заменим ее на две элементарных конъюнкции (x  y) и (x   y), В результате получим ДНФ А = x  y  x   y  x  y  y   y.

Так как теперь ДНФ А содержит две одинаковых элементарных конъюнкции x  y, то отбросим лишнюю. В результате получим ДНФ A = x  y  x   y  y   y.

Так как элементарная конъюнкция y   y содержит переменную у и ее отрицание, то y   y = 0, и ее можно отбросить как нулевой член дизъюнкции.

Таким образом, получаем СДНФ А = x  y  x   y.

Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма

Элементарной дизъюнкцией п переменных называется дизъюнкция переменных или их отрицаний.

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

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

Например, для формулы А =  (х  у)  х  у имеем:

А = ( (х  у)  х  у)  (х  у   (х  у)) =

= (х  у  х  у)  ( (х  у)   (х  у)) =

= (х  х  у)  (х  у  у)  ( х   у   х)  (  х   у   у) , то есть

КНФ А = (х  х  у)  (х  у  у)  ( х   у   х)  (  х   у   у).

Но так как х  х = х, у  у = у,  х   х =  х,  у   у =  у, то

КНФ A = (х  у)  (х  у)  ( х   у)  (  х   у).

А так как (х  у)  (х  у) = х  у, ( х   у)  (  х   у) = (  х   у), то

КНФ A = (х  у)  (  х   у).

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

Все элементарные дизъюнкции, входящие в КНФ А , различны.
Все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные.
Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит двух одинаковых переменных.
Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и ее отрицание.

Можно доказать, что каждая не тождественно истинная формула имеет единственную СКНФ.

Один из способов получения СКНФ состоит в использовании таблицы истинности для формулы  А. Действительно, получив с помощью таблицы истинности СДНФ  А, мы получим СКНФ А, взяв отрицание  (СДНФ  А), то есть СКНФ А =  (СДНФ  А).

Другой способ получения СКНФ, использующий равносильные преобразования, состоит в следующем:

Путем равносильных преобразований формулы А получают одну из КНФ А.
Если в полученной КНФ А входящая в нее элементарная дизъюнкция В не содержит переменную х_i, то, используя закон В  (x_i  x_i) = В, элементарную дизъюнкцию В заменяют на две элементарные дизъюнкции В  x_i и В   x_i, каждая из которых содержит переменную x_i.
Если в КНФ А входят две одинаковых элементарных дизъюнкции В, то лишнюю можно отбросить, пользуясь законом В  В = В.
Если некоторая элементарная дизъюнкция, входящая в КНФ А, содержит переменную x_i дважды, то лишнюю можно отбросить, пользуясь законом x_i  x_i = x_i.
Если некоторая элементарная дизъюнкция, входящая в КНФ А, содержит переменную x_i, и ее отрицание, то x_i   x_i = 1 и, следовательно, вся элементарная дизъюнкция имеет значение 1, а поэтому ее можно отбросить, как истинный член конъюнкции.

Ясно, что после описанной процедуры будет получена СКНФ А. Например, для формулы А = x  y  (x   y) КНФ А = x  (y  (x   y)) = (x  y)  (x  x   y). Так как обе элементарные дизъюнкции содержат все переменные (x и y), то первое и второе условие СКНФ выполнены. Элементарная дизъюнкция x  x   y содержит переменную х дважды, но x  x = x, поэтому КНФ А = (x  y)  (x   y); причем, ни одна из элементарных дизъюнкций не содержит переменную и ее отрицание. Значит, все условия СКНФ выполнены, и, следовательно, СКНФ А = (x  y)  (x   y).

1 2 3 4 5 6 7 8

Похожие:

	1. «Совершенные дизъюнктивные нормальные формы (сднф) и совершенные... Логика – это наука о законах мышления. Это одна из древнейших наук. Основные законы логики были сформулированы еще древнегреческим...		2. Основы логики и логические основы компьютера Основы логики. Основные... Информационные процессы в живой природе, обществе и технике: получение, передача, преобразование, хранение и использование информации....
	«Основные логические элементы» Данный урок является частью темы «Алгебра логики». Необходимость изучения данной темы обусловлена значением переключательных схем...		Рефератов по курсу «Математическая логика и теория алгоритмов» Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика
	Программа по дисциплине «прикладные протоколы интернет и www» Глобальные вычислительные сети: os unix – основные понятия, Internet – структура и основные понятия, аппаратное обеспечение, программное...		Урок №47. Формы мышления. Алгебра высказываний. Цели урока Правомерно ли считать, что религия, искусство, наука – духовные истоки философии? Обоснуйте свой ответ
	Конспект урока Тема: Алгебра логики. Решение задач с элементами алгебры логики Планируемый результат: учащиеся решат задачу на движение, используя ос решения текстовой задачи, продемонстрируют уровень усвоения...		Реферат по информатике и икт на тему: «Логика» Что такое алгебра логики стр. 4
	Тема: Основные понятия математической логики Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...		Программа предназначена для преподавателей, ведущих данную дисциплину,... Цель урока: закрепить основные понятия, рассматриваемые в законах механики Ньютона
	«Волшебный компьютер» (35 часов) Свойства информации. Язык представления информации. Кодирование информации. Основные понятия логики. Понятие графов. Устройство персонального...		Урок 1 Тема урока : Логика как наука. Основные понятия математической логики Учебный курс (рабочая программа) «Логика научного исследования» для аспирантов очной и заочной форм обучения специальностей 09. 00....
	Тема : Основные понятия математической логики А представляет собой двоичную запись числа 226, столбец значений аргумента в – числа 154, столбец значений аргумента с – числа 75....		Урок лекция План проведения урока Новое время (индуктивная логика, гипотетико-дедуктивный метод); возникновение математической логики в сер. 19 века. Соотношение традиционной...
	Программа по формированию навыков безопасного поведения на дорогах... Цели Помочь учащимся осознать понятия: грех, гордость, смирение на примере отрывка из Священной истории «Мытарь и Фарисей», высказываний...		Программа по формированию навыков безопасного поведения на дорогах... Мотивы, которые побудили выбрать тему «Алгебра логики и логические элементы персонального компьютера» для создания данного комплекса...

Школьные материалы