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

Презентация к уроку «Нормальные формы для формул алгебры логики»
презентация к уроку

Презентацияк уроку по дисциплине ЕН.02 Элементы математической логики на тему «Нормальные формы для формул алгебры логики». Тема расчитана на 2 академических часа.

Скачать:

Вложение	Размер
normalnye_formy_algebry_vyskazyvaniy.pptx	547.83 КБ

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

Подписи к слайдам:

Элементы математической логики Раздел 2. Логика (алгебра) высказываний

Нормальные формы для формул алгебры высказываний Лекция 4

2.1. Нормальные формы для формул алгебры высказываний Одна и та же логическая формула может быть записана различным образом. Например, функция F ( A , B ) может быть записана следующими эквивалентными выражениями: Эквивалентность этих формул легко проверить по таблицам истинности или выполнив необходимые преобразования.

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

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

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

Алгоритм приведения к НФ Для приведения формулы к нормальной форме используют законы логики и правила логических преобразований по следующему алгоритму: Устранить «↔» и «→ ». Продвинуть отрицание до пропозициональной переменной. Применить закон дистрибутивности. Постоянно избавляться от двойных отрицаний.

Примеры : Преобразовать формулу к виду ДНФ F=F1 ˄(F2∨¬F2)∨F2˄(F1∨¬F1)

Примеры : Преобразовать формулу к виду КНФ F=F1˄( F1∨F2)∨¬F2˄(F1∨F2)

Примеры : Преобразовать формулу к виду КНФ F=((F1→(F2∨¬F3))→F4)

Примеры : Преобразовать формулу к виду ДНФ F=¬(F1˄F2)˄(F1∨F2)

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

СДНФ Совершенная дизъюнктивная нормальная форма (СДНФ) — ДНФ, удовлетворяющая условиям: Все элементарные конъюнкции различны . Нет нулевых конъюнкций . Ни одна из элементарных конъюнкций не повторяется. Каждая элементарная конъюнкция содержит все переменные или их отрицания. Примеры СДНФ: ( X  Y) (XY) (XY) (XYZ)  (X Y Z) (X Y Z ) (X YZ) (XYZ) (X 1 X 2 X 3 X 4 )  (X 1 X 2 X 3 X 4 ) (X 1 X 2 X 3 X 4 )

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

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

2. 5 . Приведение формулы алгебры высказываний к совершенной нормальной форме Способы приведения формул к совершенным формам следуют из способов задания формул алгебры высказываний – либо с помощью таблицы , либо аналитически .

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

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

Пример Пусть ПФ, содержащая переменные X , Y , Z , имеет ДНФ вида Используя аналитический способ привести к СДНФ. Решение: В соответствии с процедурой приведения к СДНФ умножим первую и вторую конъюнкции на 1

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

Пример Найти СКНФ и СДНФ для формулы Решение: Построим таблицу истинности и на ее основе составим СДНФ и СКНФ X Y Z Элементарные конъюнкции Элементарные дизъюнкции 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1

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

Примеры : Показать, что формула ( P  ( P  Q ))  Q — тавтология ( P  ( P  Q ))  Q   ( P  (  P  Q ))  Q   P  (  P  Q )  Q   P  ( P  Q )  Q  (  P  P  Q )  (  P  Q  Q ). По теорем 2.6.1 формула тождественно истинна.

Примеры : 2. Показать , что формула P  (  Q  (  P  Q )) – тождественно ложна P  (  Q  (  P  Q))  (P   Q  P)  ( (P  Q  Q). По теорем 2.6.2 формула тождественно ложна.

Задания для закрепления 5. Построить простейшую логическую формулу по заданной таблице истинности, которая имеет нулевые значения при следующих наборах переменных A , B , C : (001), (010), (011), (110 ).

5. Построить простейшую логическую формулу по заданной таблице истинности, которая принимает значение 1 при следующих наборах переменных A , B , C : (010), (101), (111). Домашнее задание

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

По теме: методические разработки, презентации и конспекты

Презентация учебного занятия по теме «Формулы приведения». Тригонометрия.

Презентация на открытое учебное занятие по теме: «Формулы приведения» 10 класс. Тригонометрия.

алгебра логики

опорные конспекты к дисциплине основы электроники и цифровой схемотехники.

Алгебра логики: минимизация булевых функций

Открытый урок по теме «Алгебра логики: минимизация булевых функций&quot.

Презентация Мастер-класс на тему: «Формула решения конфликтных ситуаций»

Цель создания презентации: апробировать модель Мастер-класса «Формула решения конфликтных ситуаций».Моё предположение состоит в следующем: атмосфера в колледжах улуч.

Презентация по информатике на тему «Элементы алгебры логики. Высказывания. Логические операции»

Презентация по информатике на тему «Элементы алгебры логики. Высказывания. Логические операции&quot.

Алгебра логики

презентация на тему: Алгебра логики.

Логические основы алгебры логики

В материале приводятся определения: алгебры логики, логического высказывания, таблиц истинности.В презентации рассказывается о логических операциях, используемых в алгебре логики.Приводятся примеры со.

Источник

Булевы функции.
презентация к уроку по теме

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

Положительным моментом является также включение библиографического, исторического материала об ученых математиках И.И. Жегалкине и Ч. Пирсе.

Данная методическая разработка применима:

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

Скачать:

Вложение	Размер
bulevy_funkciisovmestimost.pptx	2.89 МБ

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

Подписи к слайдам:

Булеву функцию одного аргумента можно определить таблицей : X’- функция называется отрицанием. X X’ 0 1 1 0 X Y X · Y X V Y X → Y X ↔ Y X | Y X ↓ Y X+Y 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 0 0 0 В таблице(ниже) приведены основные булевы функции от двух аргументов : Здесь: X · Y — конъюнкция, X V Y –дизъюнкция, X → Y – импликация, X ↔ Y – эквивалентность, X|Y – штрих Шеффера, X ↓ Y – стрелка Пирса X+Y – сумма Жегалкина .

Иван Иванович Жегалкин (1869-1947) – российский математик и логик, один из основоположников современной математической логики. Из его открытий наибольшую известность получил так называемый полином Жегалкина. Жегалкин награжден Орденом Трудового Красного Знамени. В своем письме М. Я. Выгодскому известный советский математик Николай Лузин, вспоминая студенческие годы, говорит, что из профессоров не боялся лишь Жегалкина. Чарльз Сандерс Пирс (1839-1914)- американский философ, логик, математик, основоположник прагматизма и семиотики. Ввёл в философию термин фанерон , предложил концепцию тихизма . В логику — стрелку Пирса, в картографию — проекцию Пирса. Немецкий философ Апель назвал Пирса «Кантом американской философии».

Число булевых функций n аргументов равно . Для задания булевой функции нужно указать её значение для каждого из 2 в степени n различных значений её аргументов. Если значение функции равно 0, то такая функция постоянна и называется константой 0. Если значение функции равно 1, то такая функция называется константой 1. Для функций справедливы равенства: a v a = a; aa=a a v b = b v a; ab=ba (a v b) v c = a v (b v c); (ab)c=a(bc) a v 1 = 1, a ·1=1 a v (b · c)=(a v b) ·( a v c) a · (b v c)=(a · b) v (a · c) a v (b · a)=a; a · (b v a) (X v Y)’=X’ · Y’; (X · Y)’=X’ v Y’ X v X’ = 1; X · X’= 0 X’’=X a v 0 = a; a · 0 = 0 a → b=a’ v b’ a ↔b =(a → b) ·(b → a)

Все приведённые выше формулы проверяются с помощью таблиц булевых функций. Докажем последнюю формулу. 1. Составим таблицу : a b a ↔ b a → b b → a (a → b) ·( b → a) 0 0 1 1 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 1 2. Сравним третий и шестой столбцы, видим, что они одинаковы, значит функции стоящие в левой и правой части доказываемой формулы, принимают одинаковые значения для одинаковых наборов аргументов

Конъюнктивным(дизъюнктивным) одночленом от переменных ( , , … ) называется конъюнкция(дизъюнкция) этих переменных или их отрицаний. Формула, равносильна данной формуле алгебры высказываний и являющаяся дизъюнкцией элементарных произведений (конъюнктивных одночленов), называется дизъюнктивной нормальной формулой(ДНФ) данной формулы: Например: ABC v A v CB v — ДНФ Формула, равносильна данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных произведений (дизъюнктивных одночленов), называется конъюнктивной нормальной формулой(КНФ) данной формулы. Например: ( v B v C )( A v ) B – КНФ.

Для каждой формулы алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм. Для этого нужно: Избавится от всех логических операций, содержащихся в формуле, заменив их основными – конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать используя равносильные формулы : A →B=A v B ;A↔B=(A v B) ∙(A’ v B’); A↔B=(A∙B) v (A’∙B’). Заменить знак отрицания, относящийся к выражениям типа АВ или А v B, знаками отрицания. Относящимся к отдельным переменным высказываниям на основании формул А v B = AB; A’B’= A’ v B’ Избавится от знаков двойного отрицания: A=A’’ Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности, формулы поглощения. Теорема: Формула алгебры высказываний является тождественно ложной тогда и только тогда, когда каждое слагаемое (т. е. каждое элементарное произведение) ее ДНФ содержит пару сомножителей, один из которых есть элемен­тарное высказывание, другой — его отрицание.

Можно построить КНФ для отрицания исходной формулы. Если окажется, что она удовлетворяет условиям теоремы, то исходная формула невыполнима, так как ее отрицание тож­дественно истинно. В не перечисленных выше случаях формулы являются вы­полнимыми. Рассмотрим, например, формулу: (a ٨ b ٨ c)(a ٨ b ٨ c)(a ٨ b ٨ c) При приведении этой формулы к КНФ среди дизъюнктивных одночленов будет а v b v с, что противоречит условию суще­ствования тавтологии . Поэтому данная формула — не тавтология. При решении ряда задач часто бывает удобно использо­вать совершенную дизъюнктивную нормальную форму функ­ции (СДНФ) или совершенную конъюнктивную нормальную форму функции (СКНФ). Одночлен от некоторых переменных называется совершен­ным, если каждая из этих переменных входит в него точно один раз либо со знаком отрицания, либо без него .

Нормальная форма от некоторых переменных называется совершенной , если каждый входящий в нее одночлен является совершенным одночленом от тех же самых переменных. Совершенной дизъюнктивной нормальной формой функции (СДНФ) будем называть функцию вида: Ф( ) = Ǝ Ф ( ) , , Где А дизъюнкция распространяется на все выражения для которых Ф ( ) =1.

Конструктивно СДНФ для каждой формулы алгебры выс­казываний, приведенной к ДНФ, можно определить так: Совершенной дизъюнктивной нормальной формой (СДНФ) формулы алгебры высказываний называется ее ДНФ, облада­ющая следующими свойствами : ДНФ не содержит двух одинаковых слагаемых . Ни одно слагаемое не содержит одновременно двух одина­ковых сомножителей . Ни одно слагаемое не содержит одновременно некоторое высказывание и его отрицание. Каждое слагаемое содержит в качестве сомножителя либо переменное высказывание, либо его отрицание для всех переменных входящих в формулу . Приведем, например, к СДНФ булеву функцию( a v b’ ) ∙ ( a→c ). Используя свойства булевых функций, получаем: ( a v b’ ) ∙ ( a→c ) = (a’ ∙ b’ )v (a’ ∙ c)=(a’ ∙ b’ ∙ a’) v (a’ ∙ b’ ∙ c)=(a’ ∙ b’) v (a’ ∙ b’ ∙ c)=a’ ∙ b‘=a’ ∙ b’(c v c’)=(a’ ∙ c ∙ b’) v (a’ ∙ c’ ∙ b’)

Совершенной конъюнктивной нормальной формой функции (СКНФ) будем называть функцию вида: Ф( ) = V Ф ( ) , , Где А конъюнкция распространяется на все выражения , для которых Ф ( ) =0 Конструктивно СКНФ для каждой формулы алгебры высказываний, приведенной к КНФ, можно определить так: Совершенной конъюнктивной нормальной формой (СКНФ) данной формулы алгебры высказываний называется такая ее КНФ, которая удовлетворяет следующим свойствам.

1.КНФ не содержит одинаковых сомножителей. 2. Ни один из сомножителей не содержит двух одинаковых слагаемых. 3. Ни один сомножитель не содержит одновременно неко­торое переменное высказывание и его отрицание. 4. Каждый сомножитель СКНФ содержит в качестве слага­емого либо переменное высказывание, либо его отрицание для всех переменных высказываний, входящих в формулу. Из определений и теорем следует, что тождественно ис­тинная формула не имеет СКНФ, а тождественно ложная не имеет СДНФ. Каждая не тождественно истинная и не тождественно лож­ная формула имеют единственные СКНФ и СДНФ. Можно доказать следующие утверждения. Каждая булева функция от п переменных, отличная от константы 0, имеет единственную (с точностью до пе­рестановки дизъюнктивных членов) СДНФ. Каждая булева функция от п переменных, отличная Щ константы 1, имеет единственную (с точностью до пе­рестановки конъюнктивных членов) СКНФ .

Рассмотрим обратную задачу. Задана некоторая функция f( , … ) своей таблицей истинности, нужно построить для нее формулу. Задача эта неоднозначна, существует множество равносильных между собой формул, соответствующих данной функции. Будем строить СДНФ. СДНФ содержит столько слагаемых, сколько единиц име­ет истинностная таблица. Эти единицы соответствуют тем на- борам переменных, при которых каждое слагаемое (‘элемен­тарная конъюнкция) обращается в единицу, т. е. переменным, входящим в элементарную конъюнкцию без знака отрицания, соответствует 1, а со знаком отрицания 0. Чтобы написать СКНФ по заданной истинностной таблице, нужно выбрать все встречающиеся в ней значения 0 и рассмот­реть наборы значений переменных, отвечающие этим нулям. СДНФ содержит столько сомножителей, сколько нулей имеет истинностная таблица. Эти нули соответствуют тем на* борам переменных, при которых каждый сомножитель (каж­дая элементарная сумма) обращается в нуль, т. е. переменным , входящим в элементарную сумму без знака отрицания, соответствует 0, а со знаком отрицания 1…

Построим, СДНФ и СКНФ для формулы A=( p → q ) ^ (p v q). Для решения задачи используем истинную таблицу для А. p q q p → q p v q ( p → q )^(p v q) 1 1 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 В таблице отметим строки, где А принимает значение 1(3 и 4 строки). В третьей строке А=1, если р=1, q=0, составим конъюнкцию p ^ В четвертой строке А=1 если p=0, q=1, следовательно p ^ q . Полученные конъюнкции соединим законом дизъюнкции и получим СДНФ. B=(p ^ q) v (p ^ q)

Отметим в таблице строки, в которых А = 0. Это втора и пятая строки. Составим дизъюнкции: для второй строки v для пятой строки p v q. Соединив дизъюнкции конъюнкцией, получим СКНФ: С=( p v q ) ^ (p v q) Если построить истинные таблицы то можно проверить эквивалентности А и В, А и С. p q q p → q p v q ( p → q )^(p v q) 1 1 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 Например используя СКНФ, найдем булеву функцию, принимающую значение 0 на следующих наборах переменных, и только на них: f(0,0,0)=f(0,1,0)=f(0,1,1)=0

Выпишем наборы переменных при которых булева функция обращается в нуль:(0,0,0),(0,1,0),(0,1,1). Для каждого набора выпишем совершенный, дизъюнктивный одночлен, обращающейся в нуль только на этом наборе переменных: f(0,0,0)=0 если a v b’ v c; f(0,1,0 )= 0 если a v b’ v c ; f(0,1,1)=0 Если a ’ v b ’ v c’. Соединяя полученные совершенные дизъюнктивные одночлены конъюнкцией, получим СКНФ: f(a, b, c)= (a v b v c) (a v b’ v c) (a v b’ v c) Система булевых функций называется полной, если любая функция может быть выражена через функции c помощью суперпозиций. Пусть К° = < >— конечная си­стема булевых функций. Функция / называется элементарной суперпозицией ( перпозицией ранга 1) функций f 1 , f 2 , . f m если /может быть получена одним из следующих способов: а) переименованием некоторой переменной х, какой-ни­будь функции f i . б) подстановкой некоторой функции f i (1 i т) вмес­то какой-либо переменной х. любой из функций . Суперпозиции ранга 1 образуют класс функций К 1 . Класс функций, получающийся из функций класса К*

1 суперпози­цией ранга s — 1 с помощью элементарных суперпозиций, называется классом функций К 3 суперпозиций ранга s . Суперпо­зициями функций из К 0 называются функции, входящие в какой-то из классов К\ Согласно введенным определениям, можно говорить, что система булевых функций полна. Тогда любую булеву функцию можно представить в виде многочлена от своих переменных. Многочленом Жигалкина называется многочлен, являющий­ся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой сте­пени .

Теорема : Любая функция булевой алгебры может быть представлена, и притом единственным образом, с помощью по­линома Жигалкина вида J = . Представим, например, виде полинома выражение вида Х 1 v Х 2 . Для этого проведем следующие рассуждения. Пусть Х 1 v Х 2 = а Х 1 Х 2 + b Х 1 + сХ 2 + k , где а , b , с, k — неопределенные коэффициенты. При Х 1 = Х 2 = 0 имеем к = 0. При Х 1 = 1, Х 2 = 0 имеем b = 1. При Х 1 = 0 , Х 2 = 1 имеем с = 1. При Х 1 = Х 2 = 1 имеем а + b + с = 1, т. е. а = — 1 . Таким образом, получаем: Х 1 v Х 2 = — Х 1 Х 2 + Х 1 + Х 2 . Пусть дана булева функция f ( x 1 … x k ) . Функция f* ( x 1 … x 1 ) на­зывается двойственной если f* ( x 1 … x k ) = Двойственной к f ( x 1 ) = 0 является f ( x 2 ) = 1 и , наоборот, двойственной к a v b , является а ^ b и наоборот. Функция называется самодвойственной , если f ( x 1 .. x k ) = f ‘( x 1 .. x k ). Функция называется линейной , если f( ) = a 0 + a 1 х … + a k x k , где a i < 1,0>. Функция называется монотонной , если для любых из списка переменных таких, что , имеем f ( ) f ( ). Множество К булевых функций называется функционально замкнутым , если вместе с функциями из этого класса он содержит все их суперпозиции. Справедливо следующее утверждение: никакая полная сис­тема булевых функций не может содержаться в функционально замкнутом классе отличном от класса К 1 всех булевых функций. Функционально замкнутыми являются следующие классы: Т 0 — класс функций, сохраняющих 0 ( f(0 , 0, . 0) = 0); Т 1 — класс функций, сохраняющих 1 ( f ( 1, 1, . 1) = 1); S — класс самодвойственных функций; L — класс линейных функций; М —класс монотонных функций. Теорема Поста: Для того чтобы система бу­левых функций < f x , f v … f m >была полной, необходимо и доста­точно, чтобы для каждого из классов Т 0 , Т 1 , S , L , М нашлась функция f i не принадлежащая этому классу.

Докажем, например, полноту системы <+, V, 1>. Составим таблицу Поста (ниже): в клетках таблицы будем писать + или — в зависимости от того, принадлежит рассматриваемая функция выбранному замкнутому классу или нет. Согласно теореме Поста, для полноты системы необходи­мо и достаточно, чтобы в каж д ом столбце был хотя бы один минус. Следовательно, рассматриваемая система полна. Система функций W называется независимой, если ника­кая функция f W не представляется суперпозициями фун­кций из множества W \ < f >. Независимая система функций на­зывается базисом функционального замкнутого класса К, если всякая функция из К — суперпозиция функций из W . Например, система функций <+, •, 1>независимая, так как + • , 1 , + L, • L, 1 L, + , • , 1 f S L M A + B + — — + — A v B + + — — + 1 — + — + + f S L M A + B + — — + — A v B + + — — + 1 — + — + +

Источник