Дискретная математика решить логическое уравнение

Дискретная математика решить логическое уравнение

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

Примеры логических выражений

С применением отрицания

Со знаком «эквивалентно»

Со знаком «следствие»

С применением конъюкции и дизъюнкции

С применением Не-и и Не-или

В калькуляторе вы сможете упростить выражения, содержащие следующие операции: NOT, XOR, AND, OR, NAND, NOR, NOT

© Контрольная работа РУ — калькуляторы онлайн

Где учитесь?

Для правильного составления решения, укажите:

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

Содержание:

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

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

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

Понятие высказывания Алгебра логики изучает свойства функций, у которых и аргументы, и значения принадлежат заданному двухэлементному множеству (например,). Иногда вместо термина «алгебра логики» употребляют термин «двузначная логика». Отцом алгебры логики по праву считается английский математик XIX столетия Джордж Буль.

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

Существуют алгебры натуральных чисел, многочленов, векторов, матриц, множеств и т. д. Дж. Буль (1815-1864) Долгое время алгебра логики была известна достаточно узкому классу специалистов.

По этой ссылке вы найдёте полный курс лекций по высшей математике:

Прошло почти 100 лет со времени создания алгебры логики Дж. Булем, прежде чем в 1938 году выдающийся американский математик и инженер Клод Шеннон (1916-2001) показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе функционирования ре-лейно-контактных и электронно-ламповых схем. Исследования в алгебре логики тесно связаны с изучением высказываний (хотя высказывание — предмет изучения формальной логики).

• С помощью высказываний мы устанавливаем свойства, взаимосвязи между объектами. Высказывание истинно, если оно адекватно отображает эту связь, в противном случае оно ложно. Примерами высказываний на естественном языке являются предложения «Сегодня светит солнце» или «Трава растет». Каждое из этих высказываний характеризует свойства или состояние конкретного объекта (в нашем примере погоды и окружающего мира). Каждое из этих высказываний несет значение «истина» или «ложь».

Однако определение истинности высказывания далеко не простой вопрос. Например, высказывание «Число — простое», принадлежащее Ферма (1601-1665), долгое время считалось истинным, пока в 1732 году Эйлер (1707-1783) не доказал, что оно ложно. В целом, обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания «Сумма углов треугольника равна » устанавливается геометрией, причем в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского — ложным. Что же является высказыванием в формальной логике?

Определение 1. Высказывание — это языковое образование, в отношении которого имеет смысл говорить о его истинности или ложности (Аристотель).

Возможно вам будут полезны данные страницы:

Это словесное определение, не являющееся математически точным, только на первый взгляд кажется удовлетворительным. Оно отсылает проблему определения высказывания к проблеме определения истинности или ложности данного языкового образования. Если рассматривать в качестве высказываний любые утвердительные предложения, то это быстро приводит к парадоксам и противоречиям. Например, предложению «Это предложение является ложным» невозможно приписать никакого значения истинности без того, чтобы не получить противоречие. Действительно, если принять, что предложение истинно, то это противоречит его смыслу. Если же принять, что предложение ложно, то отсюда следует, что предложение на самом деле истинно.

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

Определение 2. Высказывание называется простым (элементарным)I, если никакая его часть не является высказыванием.

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

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

Логические операции. Таблицы истинности

Употребляемые в обычной речи связки «и», «или», «не», «если . то . », «тогда и только тогда, когда . » и т. п. позволяют из уже заданных высказываний строить новые сложные высказывания. Истинность или ложность получаемых таким образом высказываний зависит от истинности и ложности исходных высказываний и соответствующей трактовки связок как логических операций над высказываниями. Для обозначения истинности, как правило, используются символы «И» и «1», а для обозначения ложности — символы «Л» и «0».

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

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

Например, сообщая: <Ивановы привезли на зиму уголь и закупили дрова на растопку камина>, мы выражаем в одном высказывании свое убеждение в том, что произошли оба этих события.

Определение 3. Конъюнкция — логическая операция, ставящая в соответствие каждым двум элементарным высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.

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

Рассмотрим два высказывания = <Завтра будет мороз) и <Завтра будет идти снег>. Очевидно, новое высказывание = <Завтра будет мороз, и завтра будет идти снег>истинно только в том случае, когда одновременно истинны высказывания а именно, когда истинно, что завтра будет и мороз, и снег.

Высказывание будет ложно во всех остальных случаях: будет идти снег, но будет оттепель (т. е. не будет мороза); мороз будет, а снег не будет идти; не будет мороза, и снег не будет идти. В русском языке конъюнкции соответствует не только союз «и», но и другие речевые обороты, например связки «а» или «но».

Высказывание, состоящее из двух высказываний, объединенных связкой «или», называется дизъюнкцией или логическим сложением, нестрогой дизъюнкцией.

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

Определение 4. Дизъюнкция — логическая операция, которая каждым двум элементарным высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны.

Логическая операция дизъюнкция определяется следующей таблицей истинности:

Дизъюнкция истинна, когда хотя бы одно из двух образующих ее высказываний истинно. Рассмотрим два высказывания = <Колумб был в Индии) и = <Колумб был в Египте>. Очевидно, новое высказывание = <Колумб был в Индии или Колумб был в Египте>истинно как в случае, если Колумб был в Индии, но не был в Египте, так и в случае, если он не был в Индии, но был в Египте, а также в случае, если он был и в Индии, и в Египте. Но это высказывание будет ложно, если Колумб не был ни в Индии, ни в Египте.

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

В отличие от обычной дизъюнкции (связка «или»), в высказывании, являющемся разделительной дизъюнкцией, мы утверждаем, что произойдет только одно событие из двух. Например, сообщая: <Петя сидит на трибуне А либо на трибуне Б>, мы утверждаем, что Петя сидит либо только на трибуне А, либо только на трибуне Б.

Определение 5. Строгая, или разделительная дизъюнкция — логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда ровно одно из двух высказываний является истинным.

Логическая операция разделительная дизъюнкция определяется следующей таблицей истинности:

Рассмотрим два высказывания — <Кошка охотится за мышами) и — <Кошка спит на диване). Очевидно, что новое высказывание истинно только в двух случаях: когда кошка охотится за мышами или когда кошка мирно спит. Это высказывание будет ложно, если кошка не делает ни того, ни другого, т. е. когда оба события не происходят. Но это высказывание будет ложным и тогда, когда предполагается, что оба события будут происходить одновременно.

Определение 6. Импликация — логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся ложным тогда и только тогда, когда условие (посылка) — истинно, а следствие (заключение) — ложно.

Логическая операция импликация задается следующей таблицей истинности:

Мы видим, что импликация заведомо истинна, если условие ложно. Другими словами, из неверного условия может следовать все, что угодно. Например, высказывание <Если то крокодилы летают) является истинным. Подавляющее число зависимостей между событиями можно описать с помощью импликации.

Примеры с решением

Пример 1.

Следующие две импликации являются ложными, так как в них посылки истинны, а заключения ложны:

Может показаться странным, что высказывание «Если А, то В>> всегда истинно, если посылка (высказывание Л) ложна. Но для математика это вполне естественно. В самом деле, исходя из ложной посылки, можно путем верных рассуждений получить как истинное, так и ложное утверждение. Допустим, что 1 = 2, тогда и 2 = 1. Складывая эти равенства, получим 3 = 3, т. е. из ложной посылки путем тождественных преобразований мы получили истинное высказывание.

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

Логические формулы. Законы алгебры логики

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

Определение 9. Логической переменной называется переменная, значением которой может быть любое высказывание.

Логические переменные (далее «переменные») обозначаются латинскими буквами, иногда снабженными индексами, как обычные алгебраические переменные: и т. п.

Понятие логической формулы является формализацией понятия сложного высказывания. Введем его индуктивно. Определение 10. Логической формулой является: 1) любая логическая переменная, а также каждая из двух логических констант — 0 (ложь) и 1 (истина); 2) если А и В — формулы, то В и А*В — тоже формулы, где знак «*» означает любую из логических бинарных операций. Формулой является, например, следующее выражение: Каждой формуле при заданных значениях входящих в нее переменных приписывается одно из двух значений — 0 или 1.

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

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

1) законы коммутативности

2) законы ассоциативности

3) законы поглощения (нуля и единицы)

4) законы дистрибутивности

5) закон противоречия

6) закон исключенного третьего

7) законы идемпотентности

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

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

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

Любой из этих законов может быть легко доказан с помощью таблиц истинности.

Пример 2.

Докажем первый закон де Моргана с использованием таблиц истинности. Построим таблицу истинности для левой и правой частей закона.

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

Пример 3.

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

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

Пусть истинна левая часть. Тогда по определению дизъюнкции истинна или формула или формула или обе эти формулы одновременно.

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

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

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

Рассмотрим, как можно использовать данный способ для решения задач.

Пример 4.

Задача «Уроки логики». На вопрос, кто из трех учащихся изучал логику, был получен ответ: «Если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй». Кто из учащихся изучал логику?

Решение. Обозначим через высказывания, состоящие в том, что соответственно первый, второй, третий учащийся изучали логику. Из условия задачи следует истинность высказывания Воспользуемся соотношением и упростим исходное высказывание:

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

Пример 5.

Задача «Кто виноват?» По обвинению в ограблении перед судом предстали Иванов, Петров, Сидоров. Следствием установлено: 1) если Иванов не виновен или Петров виновен, то Сидоров виновен; 2) если Иванов не виновен, то Сидоров не виновен. Виновен ли Иванов? Решение. Рассмотрим простые высказывания: А = <Иванов виновен>, В = <Петров виновен>, С = <Сидоров виновен>. Запишем на языке алгебры логики факты, установленные следствием: Обозначим — единое логическое выражение для всех требований задачи. Оно истинно. Составим для него таблицу истинности:

Решить данную задачу — значит указать, при каких значениях А полученное сложное высказывание F истинно. Для этого необходимо проанализировать все строки таблицы истинности, где И если хотя бы в одном из таких случаев (Иванов не виновен), то у следствия недостаточно фактов для того, чтобы обвинить Иванова в преступлении. Анализ таблицы показывает, что высказывание истинно только в тех случаях, когда истинно, т. е. Иванов в ограблении виновен. Иногда, для того чтобы решить задачу, нет необходимости составлять единое логическое выражение, удовлетворяющее всем условиям задачи, достаточно построить таблицу истинности, отражающую каждое условие задачи, и проанализировать ее.

Присылайте задания в любое время дня и ночи в ➔

Официальный сайт Брильёновой Натальи Валерьевны преподавателя кафедры информатики и электроники Екатеринбургского государственного института.

Все авторские права на размещённые материалы сохранены за правообладателями этих материалов. Любое коммерческое и/или иное использование кроме предварительного ознакомления материалов сайта natalibrilenova.ru запрещено. Публикация и распространение размещённых материалов не преследует за собой коммерческой и/или любой другой выгоды.

Сайт предназначен для облегчения образовательного путешествия студентам очникам и заочникам по вопросам обучения . Наталья Брильёнова не предлагает и не оказывает товары и услуги.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что умеет калькулятор

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

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы задать функцию через вектор значений необходимо записать вектор из 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. Построим таблицу истинности для функции

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

Найдём наборы, на которых функция принимает истинное значение: < 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 строк:

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

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

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

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

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

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