Что такое таблица истинности?
Таблица истинности — это таблица, описывающая логическую функцию, а именно отражающую все значения функции при всех возможных значениях её аргументов. Таблица состоит из 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 дней.
Заказать решение задач по булевым функциям легко