Упрощение логических выражений

Закон 11 (поглощения)

Примеры

Примеры

Упростить выражение

Практические задания

Упростить выражение:

1 вариант	2 вариант
1)	1)
2)	2)
3)	3)
4)	4)
5)	5)
6)	6)
7)	7)
8)	8)

Контрольные вопросы

1.Основные законы логики

2.Порядок выполнения логических операций

Список литературы

1.Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая логика. — М.: Финансы и статистика, 2006. — 368 с.

2.Варпаховский Ф.Л. Элементы теории алгоритмов. - М., Просвещение, 1970. - 25 с. (МГЗПИ)

3.Гуц А.К. Математическая лоrика и теория алrоритмов. - Омск: Издательство Наследие. Диалог-Сибирь, 2003. - 108 с.

4.Босс В. Лекции по математике. Т. 6: От Диофанта до Тьюринга. - М.: КомКнига, 2006. - 208 с.

5.Босс В. Лекции по математике. Т. 10: Перебор и эффективные алгоритмы: Учебное пособие. — М.: Издательство ЛКИ, 2008. - 216 с.

Практическое занятие № 15

Приведение формул к совершенным нормальным формам

Тема программы: Нормальные формы для формул алгебры высказываний.

Цели работы:

1) Обобщить теоретические знания по теме: «Приведении формул к совершенным нормальным формам».

2) Рассмотреть алгоритмы решений заданий теме «Блок-схемы и программы реализующих построение совершенных нормальных форм».

3) Формировать умение ставить цели и реализовывать их.

Время выполнения:1 час.

Теоретические основы

Элементы математической логики

Логика высказываний

Высказыванием называется повествовательное предложение, о котором можно сказать в данный момент, что оно истинно или ложно, но не то и другое одновременно. Истинность или ложность предложения есть истинное значение высказывания. Сопоставим каждому высказыванию переменную равную 1, если оно истинно и равную 0 если оно ложно. Если P и Q – некоторые высказывания, то можно образовать высказывания “P или Q”, “P и Q”, “не P”, введя операции дизъюнкции ( ), конъюнкции(&) и отрицания. Действия этих операций задаются таблицами истинности (таб. 1-3), каждой строке которых взаимно однозначно соответствуют набор значений составляющих высказываний и соответствующее значение составного высказывания.

Таблица 1 Таблица 2 Таблица 3

P	Q	P Q	P	Q	P&Q	P
0	0	0	0	0	0	0	1
0	1	1	0	1	0	1	0
1	0	1	1	0	0
1	1	1	1	1	1

Операции дизъюнкции, конъюнкции и отрицания читаются как «или», «и» и «не».

Приведем основные законы, определяющие эти операции:

закон идемпотентности дизъюнкции и конъюнкции

(1)

закон коммутативности дизъюнкции и конъюнкции

(2)

закон ассоциативности дизъюнкции и конъюнкции

(3)

закон дистрибутивности конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции

(4)

закон двойного отрицания

(5)

законы де Моргана

(6)

законы склеивания

(7)

законы поглощения

(8)

законы Порецкого

(9)

Законы, определяющие действия с константой

(10)

Всякое высказывание, построенное с помощью операций «и», «или», «не», имеет некоторое истинное значение, зависящее от значений составляющих высказываний. Любое высказывание f может быть задано в виде таблицы истинности. Если значение высказывания зависит от n составляющих высказываний x₁,x₂,x₃,…x_n, то таблица истинности содержит 2ⁿ строк. Составляющие высказывания x_i будем называть атомарными высказываниями или просто переменными x_i, рассматривая при этом сложное высказывание как функцию f от n переменных.

Построение совершенных нормальных форм.

Исчисление высказываний можно построить используя соответствующие таблицы истинности. Алгебра Буля простейшая в классе булевых алгебр; она является двухэлементной булевой алгеброй. Одним из элементов двухэлементной булевой алгебры является 0, так как булева алгебра является решеткой с дополнениями, поэтому вторым элементом этой алгебры является 1.

Каждое высказывание и соответствующую ему булеву функцию f (x₁,x₂,…x_n) можно представить в виде дизъюнкции конституент , где

Пример 1. Рассмотрим пример высказывания f(x₁,x₂,x₃), заданное таблицей истинности (таб. 4)

Таблица 4.

x₁	X₂	x₃	f(x₁,x₂,x₃)	x₁	x₂	x₃	f(x₁,x₂,x₃)
0	0	0	0	1	0	0	0
0	0	1	0	1	0	1	1
0	1	0	0	1	1	0	1
0	1	1	1	1	1	1	1

Согласно предыдущему утверждению функция f(x₁,x₂,x₃) может быть представлена в виде:

f(x₁,x₂,x₃)= .

В дальнейшем представление булевой функции f(x₁,x₂…x_n) в виде дизъюнкции конституент будем называть совершенной дизъюнктивной нормальной формой (СДНФ) функции f(x₁,x₂…x_n).

Переменную или ее отрицание будем называть первичным термом. Количество первичных термов, которые образуют форму, называют сложностью L(f) этой формы.

Сложность СДНФ функции из примера равна 12. Для уменьшения сложности этой функции используют основные тождества алгебры Буля (законы 1-8). Согласно свойству идемпотентности дизъюнкции имеем:

f(x₁,x₂,x₃)= .

Используя свойства коммутативности, ассоциативности и дистрибутивности, получаем:

f(x₁,x₂,x₃)=

Окончательно имеем

f(x₁,x₂,x₃)=

В результате получаем сложность L(f) функции f(x₁,x₂,x₃) равную 5.

Аналогично можно каждое высказывание и соответствующую ему булеву функцию f (x₁,x₂,…x_n) представить в виде конъюнкции конституент , где

В дальнейшем представление булевой функции f(x₁,x₂…x_n) в виде конъюнкции дизъюнкций будем называть совершенной конъюнктивной нормальной формой (СКНФ) функции f(x₁,x₂…x_n).

Для примера 1 функция f(x₁,x₂,x₃) может быть представлена в виде:

f(x₁,x₂,x₃)=

Булевы функции двух переменных

Любое сложное высказывание можно представить в виде выражения, в которое входят простые высказывания (переменные) x_i операции дизъюнкции, конъюнкции, отрицания и, быть может, скобки. Рассмотрим, каким свойствам должны удовлетворять операции, с помощью которых можно выражать любое сложное выражение.

Суперпозицией системы

называется любая функция f, полученная:

а) из переименованием переменных, ;

б) подстановкой вместо некоторых переменных функции функций , ;

в) с помощью многократно применения пунктов а) и б).

Система S называется полной в P_k, если любая функция f P_k представима в виде суперпозиции этой системы; система S называется базисом, если полнота S теряется при удалении хотя бы одной функции, где P_k – k-значная логика.

Построим все булевы функции от двух переменных (таб.5)

Таблица5

переменные		Булевы функции
x₁	x₂	f₀	f₁	f₂	f₃	f₄	f₅	f₆	f₇	f₈	f₉	f₁₀	f₁₁	f₁₂	f₁₃	f₁₄	f₁₅
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Индекс i функциональной переменной f_i , i=0,1,2,….,15, равен десятичному эквивалентному набору значений этой функции, читаемой сверху вниз. Приведем эти булевы функции:

f₀(x₁,x₂)=0 – константа 0;

f₁(x₁,x₂)= конъюнкция;

f₂(x₁,x₂)= - левая коимпликация (читается «не если x_1, то x₂ );

f₃(x₁,x₂)= ;

f₄(x₁,x₂)= - правая коимпликация;

f₅(x₁,x₂)=

f₆(x₁,x₂)= - сложение по модулю 2 или функция неравнозначности, неэквивалентности;

f₇(x₁,x₂)= - дизъюнкция;

f₈(x₁,x₂)= - функция Вебба;

f₉(x₁,x₂)= - функция эквивалентности, равнозначности;

f₁₀(x₁,x₂)= - отрицание;

f₁₁(x₁,x₂)= - правая импликация (читается « если x_2, то x₁ );

f₁₂(x₁,x₂)= - отрицание;

f₁₃(x₁,x₂)= левая импликация (читается « если x_1, то x₂ );

f₁₄(x₁,x₂)= - функция Шеффера;

f₁₅(x₁,x₂)=1– константа 1.

Практические задания

1. Изучить теоретический материал по теме практического занятия

2. По заданной таблице истинности построить совершенную дизъюнктивную нормальную форму.

x₁	X₂	x₃	f(x₁,x₂,x₃)	x₁	x₂	x₃	f(x₁,x₂,x₃)
0	0	0		1	0	0
0	0	1		1	0	1
0	1	0		1	1	0
0	1	1		1	1	1

3. По заданной таблице истинности построить совершенную конъюнктивную нормальную форму.

4. Определить сложность форм и выполнить упрощение их. Объясните полученные результаты

5. Разработать блок-схему алгоритма получения СДНФ и СКНФ.

6. Реализовать на языке программирования блок-схему алгоритма получения СДНФ и СКНФ (по выбору).

7. Выписать в отчет ход выполнения работы и выводы.

Контрольные вопросы

1. Что называется высказыванием?

2. Докажите с помощью таблиц истинности основные законы алгебры Буля.

3. Что называется атомарным высказыванием?

4. Что называют совершенной дизъюнктивной нормальной формой? Как выполняется ее построение?

5. Что называют совершенной конъюнктивной нормальной формой? Как выполняется ее построение?

6. Что является сложностью формы и как ее определять.

Список литературы

1.Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая логика. — М.: Финансы и статистика, 2006. — 368 с.

2.Варпаховский Ф.Л. Элементы теории алгоритмов. - М., Просвещение, 1970. - 25 с. (МГЗПИ)

3.Гуц А.К. Математическая лоrика и теория алrоритмов. - Омск: Издательство Наследие. Диалог-Сибирь, 2003. - 108 с.

4.Босс В. Лекции по математике. Т. 6: От Диофанта до Тьюринга. - М.: КомКнига, 2006. - 208 с.

Практическое занятие № 16

Дата добавления: 2018-02-28; просмотров: 2164; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 10 11 12 13 141516 17 18 19 Следующая ⇒

Мы поможем в написании ваших работ!