Построение таблицы истинности. СДНФ. СКНФ. Полином Жегалкина
Онлайн калькулятор позволяет быстро строить таблицу истинности для произвольной булевой функции или её вектора, рассчитывать совершенную дизъюнктивную и совершенную конъюнктивную нормальные формы, находить представление функции в виде полинома Жегалкина, строить карту Карно и классифицировать функцию по классам Поста.
Калькулятор таблицы истинности, СКНФ, СДНФ, полинома Жегалкина
введите функцию или её вектор
Скрыть клавиатуру
Показать настройки
Опускать знак конъюнкции
Таблица истинности
СКНФ СДНФ
Полином Жегалкина
Классификация Поста
Минимизация, карта Карно
Фиктивные переменные
С решением
Построить
Построено таблиц, форм:
Как пользоваться калькулятором
- Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)
- Укажите действия, которые необходимо выполнить с помощью переключателей
- Укажите, требуется ли вывод решения переключателем "С решением"
- Нажмите на кнопку "Построить"
Видеоинструкция к калькулятору
Используемые символы
В качестве переменных используются буквы латинского и русского алфавитов (большие и маленькие), а также цифры, написанные после буквы (индекс переменной). Таким образом, именами переменных будут: a , x , a1 , B , X , X1 , Y1 , A123 и так далее.
Для записи логических операций можно использовать как обычные символы клавиатуры ( * , + , ! , ^ , -> , = ), так и символы, устоявшиеся в литературе ( ∧ , ∨ , ¬ , ⊕ , → , ≡ ). Если на вашей клавиатуре отсутствует нужный символ операции, то используйте клавиатуру калькулятора (если она не видна, нажмите "Показать клавиатуру"), в которой доступны как все логические операции, так и набор наиболее часто используемых переменных.
Для смены порядка выполнения операций используются круглые скобки ().
Обозначения логических операций
- И (AND): → =>
- Эквивалентность: = ~ ≡
- Штрих Шеффера: ↑ |
- Стрелка Пирса: ↓
Что умеет калькулятор
- Строить таблицу истинности по функции
- Строить таблицу истинности по двоичному вектору
- Строить совершенную конъюнктивную нормальную форму (СКНФ)
- Строить совершенную дизъюнктивную нормальную форму (СДНФ)
- Строить полином Жегалкина (методами Паскаля, треугольника, неопределённых коэффициентов)
- Определять принадлежность функции к каждому из пяти классов Поста
- Строить карту Карно
- Минимизировать ДНФ и КНФ
- Искать фиктивные переменные
Что такое булева функция
Булева функция f(x1, x2, . xn) — это любая функция от n переменных x1, x2, . xn, в которой её аргументы принимают одно из двух значений: либо 0, либо 1, и сама функция принимает значения 0 или 1. То есть это правило, по которому произвольному набору нулей и единиц ставится в соответствие значение 0 или 1. Подробнее про булевы функции можно посмотреть на Википедии.
Что такое таблица истинности?
Таблица истинности — это таблица, описывающая логическую функцию, а именно отражающую все значения функции при всех возможных значениях её аргументов. Таблица состоит из n+1 столбцов и 2 n строк, где n — число используемых переменных. В первых n столбцах записываются всевозможные значения аргументов (переменных) функции, а в n+1-ом столбце записываются значения функции, которые она принимает на данном наборе аргументов.
Довольно часто встречается вариант таблицы, в которой число столбцов равно n + число используемых логических операций. В такой таблице также первые n столбцов заполнены наборами аргументов, а оставшиеся столбцы заполняются значениями подфункций, входящих в запись функции, что позволяет упростить расчёт конечного значения функции за счёт уже промежуточных вычислений.
Логические операции
Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения более простых. В качестве основных операций обычно называют конъюнкцию (∧ или 0, 0, 1 > < 0, 1, 0 > < 0, 1, 1 > < 1, 0, 1 >
В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием:
Объединим конъюнкции с помощью дизъюнкции и получим совершенную дизъюнктивную нормальную форму:
K1 ∨ K2 ∨ K3 ∨ K4 ∨ K5 = ¬a ¬b c ∨ ¬a b ¬c ∨ ¬a bc ∨ a ¬b c ∨ abc
Построение совершенной конъюнктивной нормальной формы:
Найдём наборы, на которых функция принимает ложное значение: < 0, 0, 0 > < 1, 0, 0 >
В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием:
Объединим дизъюнкции с помощью конъюнкции и получим совершенную конъюнктивную нормальную форму:
D1 ∧ D2 ∧ D3 = (a∨b∨c) ∧ ( ¬a ∨b∨c) ∧ ( ¬a ∨ ¬b ∨c)
Построение полинома Жегалкина:
Добавим новый столбец к таблице истинности и запишем в 1, 3, 5 и 7 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 2, 4, 6 и 8 сложим по модулю два со значениями из соответственно 1, 3, 5 и 7 строк:
| a | b | c | F | 1 | |
| 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 0 | 1 | 0 | 1 | → | 1 |
| 0 | 1 | 1 | 1 | ⊕ 1 | 0 |
| 1 | 0 | 0 | 0 | → | 0 |
| 1 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 1 | 1 | 0 | 0 | → | 0 |
| 1 | 1 | 1 | 1 | ⊕ 0 | 1 |
Добавим новый столбец к таблице истинности и запишем в 1 и 2, 5 и 6 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 3 и 4, 7 и 8 сложим по модулю два со значениями из соответственно 1 и 2, 5 и 6 строк:
| a | b | c | F | 1 | 2 | |
| 0 | 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | ⊕ 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | → | 0 |
| 1 | 0 | 1 | 1 | 1 | → | 1 |
| 1 | 1 | 0 | 0 | 0 | ⊕ 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | ⊕ 1 | 0 |
Добавим новый столбец к таблице истинности и запишем в 1 2, 3 и 4 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 5, 6, 7 и 8 сложим по модулю два со значениями из соответственно 1, 2, 3 и 4 строк:
| a | b | c | F | 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | → | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | ⊕ 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | ⊕ 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | ⊕ 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | ⊕ 1 | 1 |
Окончательно получим такую таблицу:
| a | b | c | F | 1 | 2 | 3 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
Выпишем наборы, на которых получившийся вектор принимает единичное значение и запишем вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора следует записать единицу):
Объединяя полученные конъюнкции с помощью операции исключающего или, получим полином Жегалкина: c⊕b⊕bc⊕ab⊕abc
Programforyou — это сообщество, в котором Вы можете подтянуть свои знания по программированию, узнать, как эффективно решать те или иные задачи, а Воспользоваться нашими онлайн сервисами.
Таблица истинности онлайн
Данный онлайн калькулятор строит таблицу истинности для любого логического выражения. Чтобы начать, введите логическое выражение в поле ввода.
Калькулятор таблицы истинности
Примеры Очистить Ссылка
Загрузка изображения, подождите .
Составить таблицу истинности
Установить калькулятор на свой сайт
Калькулятор поддерживает следующие логические операции:
Логическая операция "не" (отрицание, инверсия)
Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ¬, либо значок восклицательного знака !. Операция отрицания является унарной (содержит один операнд) и обладает наивысшим приоритетом (выполняется первой) среди логических операций.
Таблица истинности логической операции "не" имеет вид:
Логическое "и" (конъюнкция, логическое умножение)
Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ∧, либо два значка амперсанда Операция конъюнкция является бинарной (содержит два операнда).
Таблица истинности логической операции "и" имеет вид:
Логическое "или" (дизъюнкция, логическое сложение)
Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ∨, либо два значка ||. Операция дизъюнкция является бинарной.
Таблица истинности логической операции "или" имеет вид:
Логическая операция "исключающее или" (сложение по модулю 2)
Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ⊕, либо функцию .
Таблица истинности логической операции "исключающее или" имеет вид:
Логическая операция "не и" (штрих Шеффера)
Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ↑, либо значок |.
Таблица истинности логической операции "не и" имеет вид:
Логическая операция "не или" (стрелка Пирса)
Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ↓, либо функцию .
Таблица истинности логической операции "не или" имеет вид:
Логическая операция "эквивалентность"
Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ⇔, либо конструкцию (знак меньше, знак равно, знак больше).
Таблица истинности логической операции "эквивалентность" имеет вид:
Логическая операция "исключающее не или"
Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ⊙, либо функцию .
Таблица истинности логической операции "исключающее не или" имеет вид:
Стоит отметить, что таблицы истинности для бинарных логических операций "эквивалентность" и "исключающее не или" совпадают. В случае, если указанные операции являются -арными, их таблицы истинности различаются. Отметим, что -арную операцию в наш калькулятор можно ввести только в виде соответствующей функции, например , и результат такого выражения будет отличаться от результата выражения . Потому что последнее интерпретируется как , в то время как в случае с — операция "эквивалентность" выполняется сразу с учетом всех аргументов.
Логическая операция "импликация"
Данная операция обозначается символом . Для её ввода в наш онлайн калькулятор можно использовать либо символ ⇒, либо конструкцию => (знак равно, знак больше).
Таблица истинности логической операции "импликация" имеет вид:
При формировании таблицы истинности сложного (составного) логического выражения необходимо использовать представленные выше таблицы истинности соответствующих логических операций.
Другие полезные разделы:
Оставить свой комментарий:
Мы в социальных сетях: Группа ВКонтакте | Бот в Телеграмме
Таблицы истинности логических функций и их построение
Логическая функция одно из основополагающих понятий математической логики. Она зависит от логических переменных и принимает значения из множества, от которого находится в зависимости. Логические функции булевых переменных могут принимать только два значения – 1 или 0.
Понятие таблиц истинности
Задаваться логическая функция может числовым способом, словесным описанием, картами Карно, аналитическим выражением и с помощью таблиц истинности. В последнем случае все аргументы функции следует записать в левой части таблицы, а значения, которые им соответствуют, в правой.
Определения 1 — 2
Таблица истинности – это таблица, просто и наглядно показывающая, какие значения будут у логического выражения при всевозможных наборах переменных функции.
Равносильными именуют те логические выражения с совпадающими последними столбцами таблицы истинности. Обозначают равносильные функции знаком «=».
Правила того, как следует проводить построение таблицы истинности
Несоблюдение хотя бы одного из них ведёт к очень грубой ошибке. Вот эти правила:
- Число строк таблицы должно совпадать с числом комбинаций всевозможных n логических переменных, то есть быть равным 2 n ;
- Количество столбцов таблицы должно равняться сумме числа логических переменных и числа логических операций;
- В построенный шаблон таблицы истинности должны вписываться все значения исходных переменных;
- Построение таблицы истинности выражения происходит по её столбцам, при этом обязательно учитываются правила логических операций.
Порядок действий при построении таблицы истинности для логических выражений
Порядок действий при построении таблицы истинности, какой бы ни была логическая функция, следующий:
- Определить, какое число строк и столбцов будет в будущей таблице. Делается подобное по формуламX = n + m, Y = 2 n +1. Где n – число переменных, m – чило логических операций.
- Заполнить самую верхнюю строку таблицы переменными и логическими операциями, идя слева направо. При этом приоритетность логических операций следует учитывать обязательно, иначе получится совсем не то, что нужно;
- В первых столбцах перечислить всевозможные комбинации входных значений;
- Выполняя заданные логические операции, заполнить все оставшиеся ячейки;
Ответом следует считать последний заполненный столбец таблицы.
О порядке логических операций
Лучше его представить списком. Логические операции выполняют в следующей последовательности: сначала идёт инверсия, затем конъюнкция, после этого дизъюнкция, после неё импликация, по её выполнении эквиваленция.
После них идут Штрих Шеффера и Стрелка Пирса. Первым может быть выполнено как то, так и другое.
Далее приведём несколько поучительных задач на построение таблиц истинности
Задачи 1 — 3
Сделать построение таблицы истинности для функции ((A→B) ∧ A) ↔ B
- Определяем сколько будет у нас столбцов. Количество переменных у нас 2, логических операций 4, число столбцов равно сумме 2+4 = 6.
- Определяем, сколько будет у на строк. Оно равно 2 n , плюс ещё одна строка для обозначения переменных и логических операций. У нас будет 2 n +1 = 2 2 + 1= 5;
- Заполняем первую строку. Прописываем символы переменные и логических операций;
- В двух первых столбцах записываем возможные значения переменных;
- В далее идущих столбцах записываем, какие значения принимают промежуточные функции;
- В самом последнем из столбцов записываем итоговые значения функции.
В результате всего этого у нас должно получиться:
Провести построение таблицы истинности функции (A ∨ B) ∧ – C
- Определяем сколько будет столбцов. Количество переменных у нас 3, количество логических операций 3. Складываем то и другое: 3+3 = 5.
- Определяем, количество строк. Оно равно 2n, плюс ещё одна строка для обозначения переменных и логических операций.В итоге будет 2n+1 = 2 3 + 1= 9;
- Заполняем первую строку. Прописываем символы переменные и логических операций;
- В два первые столбца вносим возможные значения наших переменных;
- В далее следующие столбцы записываем, какие значения принимают промежуточные функции;
- В последнем столбце записываем итоговые значения функции.
В итоге получим таблицу:
Сделать таблицу истинности для
(A ∧ B ↔ B ∧ C) ∨ (C → A)
Функция посложнее и таблица получится значительно больше, чем предыдущая.
- Считаем столбцы. Количество переменных 3, количество логических операций 6. Значит столбцов будет 3+6=9;
- Считаем строки. Их количество будет 2 3 +1= 9;
- Заполняем первую строку таблицы;
- В первых столбцах записываем все допустимые значения наших переменных;
- В остающихся столбцах пишем, какие наша функция принимает промежуточные значения
- В последний столбец пишем итоговые значения данной нам функции.
В итоге у нас получается таблица:
Нет времени решать самому?
