Построение таблицы истинности. сднф. скнф. полином жегалкина

Практическое применение

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

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

2. Минимизация логических выражений. ДНФ и СДНФ используются для минимизации логических выражений и упрощения работы с ними. Минимизация логических выражений позволяет уменьшить количество логических элементов, улучшить производительность вычислений и сэкономить ресурсы.

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

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

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

Метод минимизации Квайна:

4.  В СДНФ  выполняются
все операции неполного склеивания конституент единицы.

5.  Происходит поглощение импликантами
всех конституент единицы, которые участвуют в неполном склеивании.

6.  Совершаются операции неполного
склеивания и поглощения импликант с меньшим числом переменных (согласно пунктам
1 и 2).

Эта процедура
повторяется до тех пор, пока операции неполного склеивания остаются возможными.

Пример: Найти сокращенную ДНФ для функции .

Решение: Развернем СДНФ для F и пронумеруем конституенты F=.

  1
2       3      4 5      6

Затем выполняем операции
неполного склеивания.

Номерa склеиваемых конституент	Результат склеивания	Склеиваемая переменная
1 –2 1 – 3 2 – 5 3 – 4 4 – 6 5 – 6	xy yz x z	z x y y z x

Дальнейшее
склеивание невозможно и

Произведения 
 входят в начальную F, значит  — будут лишними.

Таким
образом, сокращенная ДНФ это далеко не всегда минимальная ДНФ, т.к. хоть она и
состоит из простых импликант, но среди них могут быть и лишние.

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

Тупиковых
функций в общем случае может быть несколько, и они могут иметь разное число
букв.

Минимальной
ДНФ называется
тупиковая ДНФ, имеющая минимум букв.

Импликантная
матрица
используется для определения минимальной ДНФ. При её помощи находят наборы
простых импликант, накрывающих все конституенты, а затем среди этих наборов
находят такие, что имеют минимальное число букв. Такие наборы соединяют их
знаками Ú.

Для
рассмотренного ранее примера имеем:

Постоянные импликанты
xyz
xy
yz	X		X
		X			X
			X	X
				X		X
					X	X

Итак F имеет 2 тупиковые ДНФ с одинаковым
числом букв (одна из них в таблице выделена подчеркиванием, другая – полужирным
шрифтом):

Пример. Найти минимальную ДНФ для , которая равна 1 на 1, 3, 5, 7, 14 и
15 наборах.

Решение: Запишем номера наборов в двоичном
коде:

0001 0011 0101 0111 1110 1111 

выпишем соответствующие
им конституенты:

Выполним первое склеивание:

Выполним второе склеивание:

Составляем импликантную
матрицу:

	X	X	X	X
				X		X
					X	X

Итак,
существует одна тупиковая ДНФ

Конъюнктивные нормальные формы.

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

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

Пример: ; ;  будут
элементарными суммами, а выражения ;  — нет.

Теорема № 1. Элементарная сумма равна нулю в
единственном случае, если переменным с отрицанием присвоена 1, а без отрицания
– 0.

Пример: Набор  на
котором  равна нулю будет 100, т. к. .

Теорема № 2. Для каждого набора значений переменных существует одна
лишь их элементарная сумма, которая равна 0.

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

Теорема № 3. Элементарная сумма всех n переменных, что входят в F, есть конституентой нуля.

Теорема № 4. Число конституент нуля для n переменных равно 2n.

Пример. Записать конституенту нуля для 17
набора.

Решение: Так как 17 в двоичной форме записи
выглядит как 10001, токонституента нуля —

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

Теорема №5 Любая логическая функция (кроме
«константы единицы») может быть единственным образом представлена в виде СКНФ.

Задача
представления функций в СКНФ (запись логических функций “по нулям”):

2_ ДНФ ,КНФ ДНФ, СКНФ алгоритмы преобразования

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

Раскрыто понятие совершенная ДНФ и КНФ. Приведены примеры преобразований

Просмотр содержимого документа «2_ ДНФ ,КНФ ДНФ, СКНФ алгоритмы преобразования»

Логические функции, СДНФ СКНФ

1.4 Формы представления функций алгебры логики

Функции алгебры логики могут быть заданы различными способами:

— таблицей истинности — в аналитической форме- в числовой форме..

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

элементарная дизъюнкция — дизъюнктивный терм или макстерм — это дизъюнктивный терм или макстерм — это дизъюнкция произв числа попарно независимых перем Например,

элементарная конъюнкция — конъюнктивный терм или минтерм — конъюнкция произв числа попарно независимых перем. Напр, Х ₁Х ₂ Х₃ — минтерм 3-его ранг

– это не минтерм, так как перем и зависимы.

Для аналитической записи функций используют две формы:

1) Дизъюнктивную Нормальную Форму — ДНФ

2) Конъюнктивную Нормальную Форму – КНФ

ДНФ это дизъюнкция минтермов разл ранга

КНФ это конъюнкция макстермов различного ранга

Если все термы, входяшие в нормальную форму имеют одинаковый и максимальный ранг,= числу переменных функции — n, то такая форма называется совершенной. При этом, минтерм называют констинтуентой (составля) 1 (КЕ), а макстерм — конституентой 0 (КН).

— это СДНФ

— это СКНФ

Т е СДНФ есть дизъюнкция конституент 1, а СКНФ — есть конъюнкция конституент 0

Составление совершенных форм по табл истинности

Совершенные формы составляют по табл истинности функции. СДНФ : для каждого набора переменных на которых функция=1, записывают минтерм ранга n , в которых с отрицанием берутся переменные = 0 на данном наборе. Все минтермы объединены дизъюнктивно.

СКНФ =для каждого набора переменных, на которых функция=0, записывают макстерм ранга n, в кот с отрицанием берутся переменные, имеющие значение=1 на данном наборе. Все макстермы объединены конъюнктивно

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

Числовая форма для СКНФ:

Алгоритм преобразованияя в ДНФ

1) Сначала избавляемся от операций импликации, эквивалентности и неравнозначности, выразив их через логические связки ¬, & и ∨ по законам:

2) Доводят знаки отрицания до независимых переменных, используя законы де Моргана:

3) Применяя з-н дистрибутивности

преобразуют формулу к дизъюнкции элементарных конъюнкций

4) 4) Постоянно избавляются от двойных отрицаний: ДНФ A наз совершенной и обозн СДНФ, если каждая переменная формулы A входит с отрицанием или без отрицания в каждый конъюнкт точно 1 раз.

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

Если кажд слаг содер все арг или их отриц, то получ соверш дизъюнкт норм форму (СДФН), напр

Для перехода от табл истинн к СДНФ учит только те сост, для кот функц= 1. Для каждого такого сост запис элем произв всех ар. Если арг имеет зн «0», то запис его отриц. Для привед примера СДНФ имеет вид (17.4)

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

ДНФ, но не СДНФ от 3 перем

-представл импликации в виде ДНФ.

-СДНФ для импликации

-СДНФ для оп эквивалентности

-СДНФ для оп неравнозначности

Прим.1 Привести к ДНФ формулу

2. Привести ту же формулу к СДНФ. Начав преобразования с ДНФ

Нахождение СДНФ по табл истинности функции

Нахождение СКНФ по табл истинности функции

1)Отметить те строки таблицы истинности, в последнем столбце которых стоят 1.

2)Выписать для каждой отмеченной строки конъюнкцию всех переменных так: если значение некоторой переменной в данной строке — 1, то в конъюнкцию включать саму эту переменную, если равно 1, то ее отрицание.

3)Все полученные конъюнкции связать в дизъюнкцию.

1)Отметить те строки таблицы истинности, в последнем столбце которых стоят 0.

2)Выписать для каждой отмеченной строки дизъюнкцию всех переменных так: если значение некоторой переменной в данной строке= 1, то в дизъюнкцию включать саму эту переменную, если равно 0, то ее отрицание.

Как представить ДНФ в виде таблицы и графа?

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

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

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

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

Булевы функции

Параметры решения►f(x,y,z) = x → y!zx → y!zУпростить выражение

(...) — ввод скобок, x -отрицание (NOT, !, ¬), & — логическое И, AND, ∧, *, v — логическое ИЛИ, OR, ∨, = — эквивалентность, ˜, ≡, , ⊕ — сумма по модулю 2, | — штрих Шеффера, И-НЕ, AND-NOT, ↓ — стрелка Пирса, ИЛИ-НЕ, OR-NOT, ← — обратная импликация.

(…)
x
˅
&
=
→
⊕
|
↓
←
Clear

Для вложенного отрицания необходимо использовать знак !. Например, x v y = !(x v y) или x v y = x v !y
Далее
Построить схему

По найденной таблице истинности можно определить логические значения высказываний, например, при x=0, y=0, z=1
Чтобы проверить высказывание на истинность или ложность, функцию необходимо вводить без знака равно (=). Например, A+B→A&B=1, необходимо ввести A+B→A&B. Если в результате преобразований получится, что f=1, то высказывание истинно, если f=0 — ложно.

булеву функциюдизъюнкцииконъюнкцииотрицания
Область определения БФ E – конечное множество, поэтому БФ можно задать с помощью таблицы истинности, содержащей |E|=2n строк. Столбец значений БФ при этом представляет собой двоичное слово длиной 2n. Поэтому количество различных БФ n переменных равно 22n.

• x f
  0 1
  1 0

• x y f
  0 0 0
  0 1 0
  1 0 0
  1 1 1

• x y f
  0 0 0
  0 1 1
  1 0 1
  1 1 1

• x y f
  0 0 0
  0 1 1
  1 0 1
  1 1 0

• x y f
  0 0 1
  0 1 0
  1 0 0
  1 1 0

• x y f
  0 0 1
  0 1 0
  1 0 0
  1 1 1

• x y f
  0 0 1
  0 1 1
  1 0 0
  1 1 1

• x y f
  0 0 1
  0 1 1
  1 0 1
  1 1 0

Основные равносильности логики высказываний

Название	Формула
Закон исключенного третьего	X v !X ≡ И
Закон противоречия	X & !X ≡ Л
Закон коммутативности	X & Y ≡ Y & XX v Y ≡ Y v X
Закон ассоциативности	(X & Y)&Z ≡ X&(Y&Z)(X v Y) v Z ≡ X v (Y v Z)
Закон дистрибутивности	X&(Y v Z) ≡ X&Y v X&ZX v Y&Z ≡ (X v Y)&(X v Z)
Закон двойного отрицания	!!X ≡ X
Закон идемпотентности	X&X ≡ X, X v X ≡ X
Законы де Моргана	!(X v Y) ≡ !X & !Y!(X & Y) ≡ !X v !Y
Закон поглощения	X v X&Y ≡ XX&(X v Y) ≡ X
Законы склеивания	(X & Y)v(X & !Y) ≡ X(X v Y)&(X v !Y) ≡ X
Замена импликации	X → Y ≡ !X v Y
Замена эквиваленции	X = Y ≡ X&Y v !X&!Y

Пример. Упростите выражение: (x˅y˅z)→(x˅y)*(x˅z)
Упростим функцию, используя основные законы логики высказываний.
Замена импликации: A → B = !A v B
Для нашей функции:
(x v y v z)→((x v y) (x v z)) = x v y v z v (x v y) (x v z)
Упростим функцию, используя законы де Моргана: !(A v B) = !A & !B
Для нашей функции:
x v y v z = x y z
По закону дистрибутивности:
(x v y) (x v z) = x v x z v y x v y z
получаем:
f = x y z v x v x z v y x v y z
После элементарных преобразований получаем:
f = x y z v x v x z v y x v y z = x y z v x v y z
f = y z v y z v x

Полные системы функций. Базисы + Пост — основная теорема о функциональной полноте

Множество функций $A$ — полная система, если замыкание $A$ совпадает с множеством всех булевых
функций $=P_2$ (т.е. любую логическую функцию можно выразить формулой с использованием только функций
множества
$A$).

Критерий Поста формулирует необходимое и достаточное условие полноты системы булевых
функций:
Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов $T_0$,
$T_1$, $S$, $M$, $L$.
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В
качестве
примера можно назвать штрих Шеффера (отрицание конъюнкции).

Широко известны такие полные системы булевых функций:

• $\left\{\land,\lor,\neg\right\}$ (конъюнкция, дизъюнкция, отрицание) — ДНФ.
• $\left\{\land,\oplus,1\right\}$ (конъюнкция, сложение по модулю 2, константа 1) — полином Жегалкина.

Полная система функций называется базисом, если она перестаёт быть полной при исключении из неё
любого элемента. Первая из упоминавшихся выше полных систем базисом не является, поскольку согласно законам де
Моргана
либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций.
Вторая
система является базисом — все три её элемента необходимы для полноты.
Максимально возможное число булевых функций в базисе — 4.

Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса.
Например, систему $\left\{\oplus,1\right\}$ можно назвать базисом класса линейных функций.

Примеры нахождения СКНФ и СДНФ

Рассмотрим несколько примеров нахождения СКНФ и СДНФ с помощью данных таблицы истинности.

Примеры 1 — 2

Необходимо по таблице истинности записать логическую функцию.

Решение. Для того чтобы выполнить задачу будем использовать правило построения СДНФ.

Получим СДНФ, которая имеет следующий вид:

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

В результате получим:

\

Требуется представить функцию, которая задана в таблице в виде СДНФ и СКНФ.

Решение: Для начала запишем в СНДФ заданную логическую функцию. Чтобы было проще, добавим еще один вспомогательный столбец. Руководствуемся правилом составления СДНФ и учитываем, что требуется ввести знак отрицания, если значение переменной будет нулевым. Это нужно для того, чтобы они не превратили в нули основной функции значение конъюнкции.

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

\

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

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

Способы представления булевой функции

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

• Совершенная дизъюнктивная нормальная форма (СДНФ)
• Совершенная конъюнктивная нормальная форма (СКНФ)
• Алгебраическая нормальная форма (АНФ, полином Жегалкина)

Совершенная дизъюнктивная нормальная форма (ДНФ)

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

Например, ДНФ является функция ¬abc ∨ ¬a¬bc ∨ ac, но не является СДНФ, так как в последней конъюнкции отсутствует переменная b.

Совершенная конъюнктивная нормальная форма (КНФ)

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

Например, КНФ является функция (a ∨ b) ∧ (a ∨ b ∨ c), но не является СДНФ, так как в первой дизъюнкции отсутствует переменная с.

Алгебраическая нормальная форма (АНФ, полином Жегалкина)

Алгебраическая нормальная форма, полином Жегалкина — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции, а в качестве сложения — исключающее ИЛИ.

Примеры полиномов Жегалкина: 1, a, a⊕b, ab⊕a⊕b⊕1

Алгоритм построения СДНФ для булевой функции

1. Построить таблицу истинности для функции
2. Найти все наборы аргументов, на которых функция принимает значение 1
3. Выписать простые конъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 0, то она входит в конъюнкцию с отрицанием, а иначе без отрицания
4. Объединить все простые конъюнкции с помощью дизъюнкции

Алгоритм построения СКНФ для булевой функции

1. Построить таблицу истинности для функции
2. Найти все наборы аргументов, на которых функция принимает значение 0
3. Выписать простые дизъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 1, то она входит в дизъюнкцию с отрицанием, а иначе без отрицания
4. Объединить все простые дизъюнкции с помощью конъюнкции

Алгоритм построения полинома Жегалкина булевой функции

Есть несколько методов построения полинома Жегалкина, в данной статье рассмотрим наиболее удобный и простой из всех.

1. Построить таблицу истинности для функции
2. Добавить новый столбец к таблице истинности и записать в 1, 3, 5… ячейки значения из тех же строк предыдущего столбца таблицы истинности, а к значениям в строках 2, 4, 6… прибавить по модулю два значения из соответственно 1, 3, 5… строк.
3. Добавить новый столбец к таблице истинности и переписать в новый столбец значения 1, 2, 5, 6, 9, 10… строк, а к 3, 4, 7, 8, 11, 12… строкам аналогично предыдущему пункту прибавить переписанные значения.
4. Повторить действия каждый раз увеличивая в два раза количество переносимых и складываемых элементов до тех пор, пока длина не станет равна числу строк таблицы.
5. Выписать булевы наборы, на которых значение последнего столбца равно единице
6. Записать вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора записать единицу) и объединить их с помощью операции исключающего ИЛИ.

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

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

Определение
1.

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

(СДНФ) – это ДНФ, в которой в каждый
конъюнктивный одночлен каждая переменная
из наборавходит ровно один раз, причем входит
либо сама,
либо ее отрицание.

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

Определение
2.

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

Определение
3.

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

(СКНФ) –
это КНФ, в которой в каждый дизъюнктивный
одночлен каждая переменная
из наборавходит ровно один раз, причем входит
либо сама,
либо ее отрицание.

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

Определение
4.

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

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

Способы
нахождения СДНФ

1-й
способ

2-й
способ

выделяем
строки, где формула принимает значение
1;

составляем
дизъюнкцию конъюнкций при условии, что
если переменная входит в конъюнкцию
со значением 1, то записываем эту
переменную, если со значением 0, то ее
отрицание. Получаем СДНФ.

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

Способы
нахождения СКНФ

1-й
способ

– с помощью равносильных преобразований:

2-й
способ

– с помощью таблиц истинности:

выделяем
строки, где формула принимает значение
0;

составляем
конъюнкцию дизъюнкций при условии, что
если переменная входит в дизъюнкцию
со значением 0, то записываем эту
переменную, если со значением 1, то ее
отрицание. Получаем СКНФ.

Пример
1.

Постройте КНФ функции
.

Решение

Исключим
связку «»
с помощью законов преобразования
переменных:

=
/законы де Моргана и двойного отрицания/
=

/дистрибутивные
законы/ =

Пример
2.

Приведите к ДНФ формулу
.

Решение

Выразим
логические операции
ичерез,и:

=
/отнесем отрицание к переменным и
сократим двойные отрицания/ =

=
/закон дистрибутивности/
.

Пример
3.

Запишите формулу
в ДНФ и СДНФ.

Решение

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

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

Помечаем
те строки таблицы, в которых формула
(последний столбец) принимает значение
1. Для каждой такой строки выпишем
формулу, истинную на наборе переменных
,,данной строки:

строка
1:
;

строка
3:
;

строка
5:
.

Дизъюнкция
этих трех формул будет принимать значение
1 только на наборах переменных в строках
1, 3, 5, а следовательно, и будет искомой
совершенной дизъюнктивной нормальной
формой (СДНФ):

Пример
4.

Приведите формулу
к СКНФ двумя способами:

а)
с помощью равносильных преобразований;

б)
с помощью таблицы истинности.

Решение:

Преобразуем
вторую элементарную дизъюнкцию:

Формула
имеет вид:

б)
составим таблицу истинности для данной
формулы:

Помечаем
те строки таблицы, в которых формула
(последний столбец) принимает значение
0. Для каждой такой строки выпишем
формулу, истинную на наборе переменных
,,данной строки:

строка
2:
;

строка
6:
.

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

Вопросы
и задачи для самостоятельного решения

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

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

3.
С помощью второго дистрибутивного
закона преобразуйте ДНФ в КНФ:

а)
;

4.
Преобразуйте заданные ДНФ в СДНФ:

5.
Преобразуйте заданные КНФ в СКНФ:

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

б)
;

Примеры использования СДНФ и СКНФ в жизни

• Анализ логических функций: С помощью СДНФ и СКНФ можно анализировать и описывать логические функции, которые находят применение в управлении системами, программировании, математике и других областях. Например, при проектировании схем управления можно использовать СДНФ для представления логических условий и правил, что упрощает понимание функциональности системы.
• Упрощение логических выражений: СДНФ и СКНФ позволяют упростить сложные логические выражения, делая их более компактными и понятными. Это может быть полезно при оптимизации программного кода, конструировании алгоритмов или разработке электрических схем. С помощью этих форм можно сократить количество элементов, улучшить производительность и общую структуру системы.
• Построение истинности таблиц: СДНФ и СКНФ используются для построения истинности таблиц, которые позволяют представить все возможные комбинации входных значений и соответствующих им выходных значений для логических функций. Это помогает анализировать и проверять работу системы в различных условиях и обнаруживать ошибки или неисправности.
• Работа с базами знаний: СДНФ и СКНФ находят применение в области искусственного интеллекта и баз знаний. Использование этих форм упрощает представление логических правил и фактов, а также поиск соответствий между ними. Например, при разработке экспертных систем, где необходимо формализовать знания экспертов и применять их для принятия решений.

Аксиоматичное построение исчисления высказываний, правило вывода (правило заключения)

Формальное определение:

• алфавит есть множество символов:
  • $а, b, …, а_1, b_1,…$ — (пропозициональные) переменные,
    значением
    которой может быть логическое высказывание;
  • $\neg, \land, \lor, \to$ (отрицание, конъюнкция, дизъюнкция и импликация) — пропозициональные
    связк;
  • (,) — скобки, служебные символы;
• формула определяется индуктивно следующим образом:
  • Если $P$ — пропозициональная переменная, то $P$ — формула.
  • Если $A$ — формула, то $\neg A$ — формула.
  • Если $A$ и $B$ — формулы, то $A \to B$, $A \land B$ и $A \lor B$ — формулы.
  • Других соглашений нет.
• Одним из возможных вариантов является следующая система аксиом:

1. $A \to (B \to A)$;
2. $((A \to (B \to C)) \to ((A \to B) \to (A \to C)))$;
3. $A \land B \to A$;
4. $A \land B \to B$;
5. $A \to (B \to (A \land B))$;
6. $A \to (A \lor B)$;
7. $B \to (A \lor B)$;
8. $(A \to C) \to ((B \to C) \to ((A \lor B) \to C))$;
9. $\neg A \to (A \to B)$;
10. $(A \to B) \to ((A \to \neg B)\to \neg A)$;
11. $A\lor\neg A$.

вместе с единственным правилом вывода:

$\frac{A \to B, A}{B}$ (»Modus ponens» — правило заключений) — если $A$ и $A \to B$ — выводимые формулы, то $B$
также выводима.