Меню

Понятие формулы логики предикатов



Логические выражения и таблица истинности

Логические выражения и таблица истинности

Таблица истинности — таблица, показывающая, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний.

Логическое выражение — составные высказывания в виде формулы.

Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак «=».

Алгоритм построения таблицы истинности:

1. подсчитать количество переменных n в логическом выражении;

2. определить число строк в таблице по формуле m=2 n , где n — количество переменных;

3. подсчитать количество логических операций в формуле;

4. установить последовательность выполнения логических операций с учетом скобок и приоритетов;

5. определить количество столбцов: число переменных + число операций;

6. выписать наборы входных переменных;

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

Заполнение таблицы:

1. разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»;

2. разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»;

3. продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа.

Пример 1. Для формулы A/\ (B \/ ¬B /\¬C) постройте таблицу истинности.

Количество логических переменных 3, следовательно, количество строк — 2 3 = 8.

Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов — 3 + 5 = 8.

Логические выражения и таблица истинности

Пример 2. Определите истинность логического выражения F(А, В) = (А\/ В)/\(¬А\/¬В) .

1. В выражении две переменные А и В (n=2).

2. mстрок=2 n , m=2 2 =4 строки.

3. В формуле 5 логических операций.

4. Расставляем порядок действий

1) А\/ В; 2) ¬А; 3) ¬В; 4) ¬А\/¬В; 5) (А\/ В)/\(¬А\/¬В).

5. Кстолбцов=n+5=2+5=7 столбцов.

Источник

Формулы логики предикатов

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

Понятие формулы логики предикатов

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

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

Определение 21.1 (формулы логики предикатов).

1) Каждая нульместная предикатная переменная есть формула;

2) если — n-местная предикатная переменная, то есть формула, в которой все предметные переменные свободны;

3) если — формула, то — также формула. Свободные (связанные) предметные переменные в формуле те и только те, которые являются свободными (связанными) в ;

4) если — формулы и если предметные переменные, входящие одновременно в обе эти формулы, свободны в каждой из них, то выражения

также являются формулами. При этом предметные переменные, свободные (связанные) хотя бы в одной из формул , называются свободными (связанными) и в новых формулах;

5) если — формула и — предметная переменная, входящая в свободно, то выражения и также являются формулами, в которых переменная связанная, а все остальные предметные переменные, входящие в формулу свободно или связанно, остаются и в новых формулах соответственно такими же;

6) никаких других формул логики предикатов, кроме получающихся согласно пп. 1–5, нет.

Формулы, определенные в пунктах 1 и 2, называются элементарными (или атомарными). Формулы, не являющиеся элементарными, называются составными.

Например, — элементарные формулы, а

являются составными формулами. При этом в первой составной формуле предметная переменная связана, а переменные — свободные. Во второй составной формуле свободна лишь переменная , остальные — связаны. В третьей составной формуле первое вхождение переменной связано, а второе — свободно. Переменная у связана. Последнюю формулу более целесообразно было бы записать в следующем виде (заменив связанную переменную х какой-нибудь буквой, не входящей в данную формулу):

Как и в алгебре высказываний, договоримся внешние скобки у формулы не писать, если только она не является частью более сложной формулы. Отметим кстати, что на основании пунктов 1, 3 и 4 сформулированного определения всякая формула алгебры высказываний будет также и формулой логики предикатов.

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

Формулы, в которых нет свободных предметных переменных, называются замкнутыми, а формулы, содержащие свободные предметные переменные, — открытыми. Так, все приведенные выше формулы логики предикатов, кроме формулы , являются открытыми.

Примеры замкнутых формул:

Классификация формул логики предикатов

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

Превращение формулы логики предикатов в высказывание описанным выше способом (а также само получаемое высказывание) называется интерпретацией этой формулы на множестве . Итак, если формула логики предикатов замкнутая, т.е. не содержит свободных предметных переменных, то ее интерпретация состоит из одного этапа и сводится к подстановке вместо всех предикатных переменных конкретных предикатов, в результате чего формула превращается в конкретное высказывание (нульместный предикат). Если же формула логики предикатов открытая, т. е. содержит ряд свободных предметных переменных, то ее интерпретация состоит из двух этапов. Во-первых, вместо всех предикатных переменных необходимо подставить конкретные предикаты, в результате чего формула превратится в конкретный предикат, зависящий от такого количества предметных переменных, сколько было свободных предметных переменных в исходной формуле. Во-вторых, нужно придать значение каждой предметной переменной, от которой зависит получившийся предикат, в результате чего этот предикат (и, значит, вся исходная формула) превратится в конкретное высказывание (истинное или ложное).

Пример 21.2. Дадим интерпретацию формуле . В качестве множества возьмем множество всех мужчин, а вместо предикатной переменной подставим конкретный предикат, определенный на » есть отец «. Тогда исходная формула превратится в следующее (очевидно, ложное) высказывание ( есть отец ) — «у каждого мужчины есть сын». Этой же формуле можно дать и другую интерпретацию. Возьмем в качестве множество всех натуральных чисел, а вместо предикатной переменной подставим предикат » «, определенный на . Тогда исходная формула превратится в (очевидно, истинное) высказывание — «Для каждого натурального числа существует большее по сравнению с ним натуральное число».

Пример 21.3. В предыдущем примере была рассмотрена интерпретация замкнутой формулы. Дадим интерпретацию открытой формуле . В качестве множества возьмем множество всех натуральных чисел. Вместо предикатных переменных и подставим трехместные предикаты » » и » » соответственно, а вместо нульместного предиката подставим (ложное) высказывание » «. Тогда данная формула превратится в двухместный предикат (от предметных переменных ):

Читайте также:  Как понять к какому виду относится частица

Посмотрим, в какие высказывания может превращаться данный предикат при подстановке вместо его переменных и конкретных предметов (чисел) из . Нетрудно понять, что двухместный предикат превращается в истинное высказывание при любой подстановке вместо его предметных переменных и натуральных чисел. В самом деле, для натуральных тип получаем высказывание

Одноместный предикат (зависит от ) , стоящий под знаком квантора , выполним, потому что всегда можно найти такое натуральное число , что и , т. е. высказывания и будут ложны, а значит, высказывание — истинно. А раз так, то высказывание истинно. Поэтому высказывание

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

Сформулируем классификационные определения для формул логики предикатов.

Определение 21.4. Формула логики предикатов называется выполнимой (опровержимой) на множестве , если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на этом множестве, она превращается в выполнимый (опровержимый) предикат.

Другими словами, формула выполнима (опровержима) на , если существует истинная (ложная) ее интерпретация на . Формула из примера 21.2 является как выполнимой, так и опровержимой.

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

Пример 21.7. Покажем, что формула является противоречием, т.е. тождественно ложной. В самом деле, допустим противное: на некотором множестве имеется конкретный предикат , такой, что данная формула превращается в выполнимый предикат (от ) . Последнее означает: найдется предмет , такой, что высказывание истинно. Истинность конъюнкции дает истинность высказываний и . Из истинности первого следует, что высказывание ложно, а из истинности второго — что предикат тождественно истинный и, значит, для любого предмета из , в том числе и для , высказывание истинно. Получаем противоречие, исключающее предположение о непротиворечивости исходной формулы. Следовательно, она тождественно ложна.

Источник

Формулы логики предикатов

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

Понятие формулы логики предикатов

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

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

Определение 21.1 (формулы логики предикатов).

1) Каждая нульместная предикатная переменная есть формула;

2) если — n-местная предикатная переменная, то есть формула, в которой все предметные переменные свободны;

3) если — формула, то — также формула. Свободные (связанные) предметные переменные в формуле те и только те, которые являются свободными (связанными) в ;

4) если — формулы и если предметные переменные, входящие одновременно в обе эти формулы, свободны в каждой из них, то выражения

также являются формулами. При этом предметные переменные, свободные (связанные) хотя бы в одной из формул , называются свободными (связанными) и в новых формулах;

5) если — формула и — предметная переменная, входящая в свободно, то выражения и также являются формулами, в которых переменная связанная, а все остальные предметные переменные, входящие в формулу свободно или связанно, остаются и в новых формулах соответственно такими же;

6) никаких других формул логики предикатов, кроме получающихся согласно пп. 1–5, нет.

Формулы, определенные в пунктах 1 и 2, называются элементарными (или атомарными). Формулы, не являющиеся элементарными, называются составными.

Например, — элементарные формулы, а

являются составными формулами. При этом в первой составной формуле предметная переменная связана, а переменные — свободные. Во второй составной формуле свободна лишь переменная , остальные — связаны. В третьей составной формуле первое вхождение переменной связано, а второе — свободно. Переменная у связана. Последнюю формулу более целесообразно было бы записать в следующем виде (заменив связанную переменную х какой-нибудь буквой, не входящей в данную формулу):

Как и в алгебре высказываний, договоримся внешние скобки у формулы не писать, если только она не является частью более сложной формулы. Отметим кстати, что на основании пунктов 1, 3 и 4 сформулированного определения всякая формула алгебры высказываний будет также и формулой логики предикатов.

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

Формулы, в которых нет свободных предметных переменных, называются замкнутыми, а формулы, содержащие свободные предметные переменные, — открытыми. Так, все приведенные выше формулы логики предикатов, кроме формулы , являются открытыми.

Примеры замкнутых формул:

Классификация формул логики предикатов

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

Превращение формулы логики предикатов в высказывание описанным выше способом (а также само получаемое высказывание) называется интерпретацией этой формулы на множестве . Итак, если формула логики предикатов замкнутая, т.е. не содержит свободных предметных переменных, то ее интерпретация состоит из одного этапа и сводится к подстановке вместо всех предикатных переменных конкретных предикатов, в результате чего формула превращается в конкретное высказывание (нульместный предикат). Если же формула логики предикатов открытая, т. е. содержит ряд свободных предметных переменных, то ее интерпретация состоит из двух этапов. Во-первых, вместо всех предикатных переменных необходимо подставить конкретные предикаты, в результате чего формула превратится в конкретный предикат, зависящий от такого количества предметных переменных, сколько было свободных предметных переменных в исходной формуле. Во-вторых, нужно придать значение каждой предметной переменной, от которой зависит получившийся предикат, в результате чего этот предикат (и, значит, вся исходная формула) превратится в конкретное высказывание (истинное или ложное).

Читайте также:  Критерии и уровень сформированности УУД

Пример 21.2. Дадим интерпретацию формуле . В качестве множества возьмем множество всех мужчин, а вместо предикатной переменной подставим конкретный предикат, определенный на » есть отец «. Тогда исходная формула превратится в следующее (очевидно, ложное) высказывание ( есть отец ) — «у каждого мужчины есть сын». Этой же формуле можно дать и другую интерпретацию. Возьмем в качестве множество всех натуральных чисел, а вместо предикатной переменной подставим предикат » «, определенный на . Тогда исходная формула превратится в (очевидно, истинное) высказывание — «Для каждого натурального числа существует большее по сравнению с ним натуральное число».

Пример 21.3. В предыдущем примере была рассмотрена интерпретация замкнутой формулы. Дадим интерпретацию открытой формуле . В качестве множества возьмем множество всех натуральных чисел. Вместо предикатных переменных и подставим трехместные предикаты » » и » » соответственно, а вместо нульместного предиката подставим (ложное) высказывание » «. Тогда данная формула превратится в двухместный предикат (от предметных переменных ):

Посмотрим, в какие высказывания может превращаться данный предикат при подстановке вместо его переменных и конкретных предметов (чисел) из . Нетрудно понять, что двухместный предикат превращается в истинное высказывание при любой подстановке вместо его предметных переменных и натуральных чисел. В самом деле, для натуральных тип получаем высказывание

Одноместный предикат (зависит от ) , стоящий под знаком квантора , выполним, потому что всегда можно найти такое натуральное число , что и , т. е. высказывания и будут ложны, а значит, высказывание — истинно. А раз так, то высказывание истинно. Поэтому высказывание

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

Сформулируем классификационные определения для формул логики предикатов.

Определение 21.4. Формула логики предикатов называется выполнимой (опровержимой) на множестве , если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на этом множестве, она превращается в выполнимый (опровержимый) предикат.

Другими словами, формула выполнима (опровержима) на , если существует истинная (ложная) ее интерпретация на . Формула из примера 21.2 является как выполнимой, так и опровержимой.

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

Пример 21.7. Покажем, что формула является противоречием, т.е. тождественно ложной. В самом деле, допустим противное: на некотором множестве имеется конкретный предикат , такой, что данная формула превращается в выполнимый предикат (от ) . Последнее означает: найдется предмет , такой, что высказывание истинно. Истинность конъюнкции дает истинность высказываний и . Из истинности первого следует, что высказывание ложно, а из истинности второго — что предикат тождественно истинный и, значит, для любого предмета из , в том числе и для , высказывание истинно. Получаем противоречие, исключающее предположение о непротиворечивости исходной формулы. Следовательно, она тождественно ложна.

Источник

Построение таблицы истинности. СДНФ. СКНФ. Полином Жегалкина.

Онлайн калькулятор позволяет быстро строить таблицу истинности для произвольной булевой функции или её вектора, рассчитывать совершенную дизъюнктивную и совершенную конъюнктивную нормальные формы, находить представление функции в виде полинома Жегалкина, строить карту Карно и классифицировать функцию по классам Поста.

Калькулятор таблицы истинности, СКНФ, СДНФ, полинома Жегалкина

введите функцию или её вектор

Построено таблиц, форм:

Как пользоваться калькулятором

  1. Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)
  2. Укажите действия, которые необходимо выполнить с помощью переключателей
  3. Укажите, требуется ли вывод решения переключателем «С решением»
  4. Нажмите на кнопку «Построить»

Видеоинструкция к калькулятору

Используемые символы

В качестве переменных используются буквы латинского и русского алфавитов (большие и маленькие), а также цифры, написанные после буквы (индекс переменной). Таким образом, именами переменных будут: a , x , a1 , B , X , X1 , Y1 , A123 и так далее.

Для записи логических операций можно использовать как обычные символы клавиатуры ( * , + , ! , ^ , -> , = ), так и символы, устоявшиеся в литературе ( ∧ , ∨ , ¬ , ⊕ , → , ≡ ). Если на вашей клавиатуре отсутствует нужный символ операции, то используйте клавиатуру калькулятора (если она не видна, нажмите «Показать клавиатуру»), в которой доступны как все логические операции, так и набор наиболее часто используемых переменных.

Для смены порядка выполнения операций используются круглые скобки ().

Обозначения логических операций

  • И (AND): & • ∧ *
  • ИЛИ (OR): ∨ +
  • НЕ (NOT): ¬ !
  • Исключающее ИЛИ (XOR): ⊕ ^
  • Импликация: -> → =>
  • Эквивалентность: =

  • Штрих Шеффера: ↑ |
  • Стрелка Пирса:
  • Что умеет калькулятор

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

    Что такое булева функция

    Булева функция f(x1, x2, . xn) — это любая функция от n переменных x1, x2, . xn, в которой её аргументы принимают одно из двух значений: либо 0, либо 1, и сама функция принимает значения 0 или 1. То есть это правило, по которому произвольному набору нулей и единиц ставится в соответствие значение 0 или 1. Подробнее про булевы функции можно посмотреть на Википедии.

    Что такое таблица истинности?

    Таблица истинности — это таблица, описывающая логическую функцию, а именно отражающую все значения функции при всех возможных значениях её аргументов. Таблица состоит из n+1 столбцов и 2 n строк, где n — число используемых переменных. В первых n столбцах записываются всевозможные значения аргументов (переменных) функции, а в n+1-ом столбце записываются значения функции, которые она принимает на данном наборе аргументов.

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

    Логические операции

    Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения более простых. В качестве основных операций обычно называют конъюнкцию (∧ или &), дизъюнкцию (∨ или |), импликацию (→), отрицание (¬), эквивалентность (=), исключающее ИЛИ (⊕).

    Таблица истинности логических операций

    a b a ∧ b a ∨ b ¬a ¬b a → b a = b a ⊕ b
    1 1 1 1
    1 1 1 1 1
    1 1 1 1
    1 1 1 1 1 1

    Как задать логическую функцию

    Есть множество способов задать булеву функцию:

    • таблица истинности
    • характеристические множества
    • вектор значений
    • матрица Грея
    • формулы

    Рассмотрим некоторые из них:

    Чтобы задать функцию через вектор значений необходимо записать вектор из 2 n нулей и единиц, где n — число аргументов, от которых зависит функция. Например, функцию двух аргументов можно задать так: 0001 (операция И), 0111 (операция ИЛИ).

    Читайте также:  Таблица виды деятельности проявление деятельности человека

    Чтобы задать функцию в виде формулы, необходимо записать математическое выражение, состоящее из аргументов функции и логических операций. Например, можно задать такую функцию: a∧b ∨ b∧c ∨ a∧c

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

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

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

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

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

    Например, ДНФ является функция ¬a bc ∨ ¬a ¬b c ∨ 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. Записать вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора записать единицу) и объединить их с помощью операции исключающего ИЛИ.

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

    Построим совершенные дизъюнктивную и дизъюнктивную нормальные формы, а также полином Жегалкина для функции трёх переменных F = ¬a b∨ ¬b c∨ca

    1. Построим таблицу истинности для функции

    a b c ¬a ¬a ∧b ¬b ¬b ∧c ¬a ∧b∨ ¬b ∧c c∧a ¬a ∧b∨ ¬b ∧c∨c∧a
    1 1
    1 1 1 1 1 1
    1 1 1 1 1
    1 1 1 1 1 1
    1 1
    1 1 1 1 1 1 1
    1 1
    1 1 1 1 1

    Построение совершенной дизъюнктивной нормальной формы:

    Найдём наборы, на которых функция принимает истинное значение: < 0, 0, 1 > < 0, 1, 0 > < 0, 1, 1 > < 1, 0, 1 >

    В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием:

    Объединим конъюнкции с помощью дизъюнкции и получим совершенную дизъюнктивную нормальную форму:

    Построение совершенной конъюнктивной нормальной формы:

    Найдём наборы, на которых функция принимает ложное значение: < 0, 0, 0 > < 1, 0, 0 >

    В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием:

    Объединим дизъюнкции с помощью конъюнкции и получим совершенную конъюнктивную нормальную форму:

    Построение полинома Жегалкина:

    Добавим новый столбец к таблице истинности и запишем в 1, 3, 5 и 7 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 2, 4, 6 и 8 сложим по модулю два со значениями из соответственно 1, 3, 5 и 7 строк:

    a b c F 1
    1 1 ⊕ 0 1
    1 1 1
    1 1 1 ⊕ 1
    1
    1 1 1 ⊕ 0 1
    1 1
    1 1 1 1 ⊕ 0 1

    Добавим новый столбец к таблице истинности и запишем в 1 и 2, 5 и 6 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 3 и 4, 7 и 8 сложим по модулю два со значениями из соответственно 1 и 2, 5 и 6 строк:

    a b c F 1 2
    1 1 1 1
    1 1 1 ⊕ 0 1
    1 1 1 ⊕ 1 1
    1
    1 1 1 1 1
    1 1 ⊕ 0
    1 1 1 1 1 ⊕ 1

    Добавим новый столбец к таблице истинности и запишем в 1 2, 3 и 4 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 5, 6, 7 и 8 сложим по модулю два со значениями из соответственно 1, 2, 3 и 4 строк:

    a b c F 1 2 3
    1 1 1 1 1
    1 1 1 1 1
    1 1 1 1 1
    1 ⊕ 0
    1 1 1 1 1 ⊕ 1
    1 1 ⊕ 1 1
    1 1 1 1 1 ⊕ 1 1

    Окончательно получим такую таблицу:

    a b c F 1 2 3
    1 1 1 1 1
    1 1 1 1 1
    1 1 1 1 1
    1
    1 1 1 1 1
    1 1 1
    1 1 1 1 1 1

    Выпишем наборы, на которых получившийся вектор принимает единичное значение и запишем вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора следует записать единицу):

    Объединяя полученные конъюнкции с помощью операции исключающего или, получим полином Жегалкина: c⊕b⊕bc⊕ab⊕abc

    А Вы знаете, что мы пишем программы на C, C++, C#, Pascal и Python?

    Так что если Вам нужно написать программу на C/C++, C#, Pascal или Python — мы с радостью поможем с этим!

    В том числе мы занимаемся репетиторством по информатике и программированию, а также готовим к ОГЭ и ЕГЭ!

    Почему именно мы?

    • Более 1800 выполненных заказов;
    • Более 170 отзывов;
    • Качественное решение
    • Короткие сроки и привлекательные цены
    • Различные акции и скидки

    Как с нами связаться?

    • группа Вконтакте: vk.com/programforyou
    • наша почта: order@programforyou.ru

    изображение с программированием для привлечения внимания

    Programforyou — доверяя нам писать программы, вы получаете качественное решение в короткие сроки по привлекательной цене!

    Источник