ПРОВЕРИТЬ СИСТЕМУ ФУНКЦИЙ НА ПОЛНОТУ ОНЛАЙН

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

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

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

Проверить на полноту систему функций.

F1(x,y)=x∼y F2(x,y)=x∨y F3(x)=¬x

Воспользуемся критерием Поста. Проверим каждую из этих функций на принадлежность к замкнутым классам P0, P1, L, S, M.

3)L-класс фунций, представимы линейным многочленом Жегалкина. F1(x,y)=x∼y=¬x¬y∨xy=¬x¬y⋅xy⊕¬x¬y⊕xy =0⊕(x⊕1)(y⊕1)⊕xy=xy⊕x⊕y⊕1⊕xy=x⊕y⊕1 Получился линейный многочлен, значит, функция принадлежит классу L

F2(x,y)=x∨y=xy⊕x⊕y – нелиненый многочлен, значит, функция не принадлжеит классу L. F3(x)=¬x=x⊕1 – линейный многочлен, значит, функция принадлежит этому классу.

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

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

В нашем случает, самодвойственной функцие является только функция F3.

Тогда, функции F1 и F3 не монотоны, а функция F2 – монотона.

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

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

Значит, наша система функций полна.

Калькуляторы по информатике

Для получения обратной польской нотации используется стек.
a+b2*c/d ≡ ab2^c*d/+

Польская инверсная запись

Диаграммы Эйлера-Венна

Диаграмма Эйлера-Венна – наглядное средство для работы со множествами. На этих диаграммах изображаются все возможные варианты пересечения множеств. Данная программа относится к таким разделам как Информатика, Дискретная математика.

Редактор схемы логических элементов

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

С помощью этого калькулятора производится минимизация булевой функции методом Карно-Вейча. Данная программа относится к таким разделам как Информатика, Дискретная математика.

Полином Жегалкина

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

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

Генерация перестановок

Выводит все возможные сочетания из N чисел: N!

Множество Парето

Находит оптимальное решение в двухкритериальной задаче.

Стоимость подключения зависит от срока использования:

Оплата осуществляется в Личном кабинете в разделе Платные услуги.

Стандарт изображений элементов

Размеры графического полотна

Созданную логическую схему можно сохранить в форматах и (меню Действия).

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

Здесь будет показано решение

Инструкция к сервису

Для добавления логического элемента необходимо выделить его левой кнопкой мыши, а затем щелкнуть мышкой на рабочем поле.
Чтобы соединить элементы, их необходимо предварительно выбрать (один клик мыши по объекту), а затем нажать на кнопку Соединить. Для соединения с переменной xi нажмите на соответствующее ей название.

Построенную схему можно сохранить в формате или .

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

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

Другие БФ строятся из элементарных с помощью суперпозиций функций.

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

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

Сократить БФ можно, применяя некоторые равносильности логики высказываний:

Метод карт Карно

Склеить можно как целиком всю карту, либо только выделенные единицы (меню Операции).

После минимизации можно получить логическую схему функции и построить таблицу истинности (кнопка Далее)

Минимизая функции через равносильные преобразования

см. таблицу равносильных преобразований

Алгоритм минимизии логической функции

По заданной СДНФ (по таблице истинности) определяются существенные и фиктивные переменные, полином Жегалкина и принадлежность классам T0,T1, S, M, L. Также можно создать новую логическую схему (если не выбран пункт Строить новую схему при минимизации булевой функции). Если вычисления происходят по исходной схеме и она понадобится в дальнейшем, то ее можно предварительно сохранить (меню Действия/Сохранить).

Название переменных можно изменить. Для этого их необходимо выбрать (первая строка таблицы).

Ввести как вектор значений (в виде строки)

Для установки параметров решения, необходимо нажать Далее.

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

пунктирная – – – –
Размеры в px и фон

Введите название переменных

Количество входов у элемента

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

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

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

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

Минимизация, карта Карно

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

Задачи и решения о классах Поста и полноте

Задача 1. Является ли полной система булевых функций, состоящая из дизъюнкции и импликации?

Задача 2. Доказать полноту (или неполноту) приведенной системы булевых функций.

$ f_1=x_1 wedge x_2,, f_2=0, , f_3=x_1 sim x_2.$

Задача 3. Определить, к каким классам Поста относится $F =
eg x1 x3 ee x1
eg x3$, добавить (если это необходимо) к $F$ элементарные функции, чтобы полученное множество было полным.

Задача 4. Является ли полной система функций?

Задача 5. а) Используя эквивалентные преобразования получить тупиковую ДНФ;
б)Построить функционально полную систему функций так, чтобы эта система была базисом и содержала $f (x, y, z, p)$

Задача 6. Проверить леммы о нелинейной, немонотонной и несамодвойственной функциях для функции

Классы Поста. Полнота системы функций

Математик Эмиль Пост ввел следующие замкнутые классы булевых функций:

Теорема Поста (о полноте): Набор булевых функций $K$ является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов $S,M,L,T0,T1$.

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

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

Полнота системы булевых функций

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

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

Другие примеры решений о булевых функциях:

Спасибо за ваши закладки и рекомендации

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

Понравилось? Добавьте в закладки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

K1 ∨ K2 ∨ K3 ∨ K4 ∨ K5 = c ∨ b ∨ bc ∨ ac ∨ abc

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

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

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

D1 ∧ D2 ∧ D3 = (a∨b∨c) ∧ (∨b∨c) ∧ (∨∨c)

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

Добавим новый столбец к таблице истинности и запишем в 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

Решение задач на заказ

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

Заказать решение задач по булевым функциям легко

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *