На данной странице будут рассмотренны 5 логических операций: конъюнкция, дизъюнкция, инверсия, импликация и эквивалентность, которых Вам будет достаточно для решения сложных логических выражений. Также мы рассмотрим порядок выполнения данных логических операций в сложных логических выражениях и представим таблицы истинности для каждой логической операции. Советуем Вам воспользоваться нашими программами для решения задач по математике, геометрии и теории вероятности. Помоми большого количества программ для решения задач на сайте работает форум, на котором Вы всегда можете задать вопрос и на котором Вам всегда помогуть с решением задач. Пользуйтесь нашими сервисами на здоровье!
Глоссарий, определения логики
Высказывание — это повествовательное предложение, про которое можно определенно сказать истинно оно или ложно (истина (логическая 1), ложь (логический 0)).
Логические операции — мыслительные действия, результатом которых является изменение содержания или объема понятий, а также образование новых понятий.
Логическое выражение — устное утверждение или запись, в которое, наряду с постоянными величинами, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных величин (объектов) логическое выражение может принимать одно из двух возможных значений: истина (логическая 1) или ложь (логический 0).
Сложное логическое выражение — логическое выражение, состоящее из одного или нескольких простых логических выражений (или сложных логических выражений), соединенных с помощью логических операций.
Логические операции и таблицы истинности
1) Логическое умножение или конъюнкция:
Конъюнкция — это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложеное выражение ложно.
Обозначение: F = A & B.
Таблица истинности для конъюнкции
| A | B | F |
| 1 | 1 | 1 |
| 1 | ||
| 1 | ||
2) Логическое сложение или дизъюнкция:
Дизъюнкция — это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выраженныя ложны.
Обозначение: F = A + B.
Таблица истинности для дизъюнкции
| A | B | F |
| 1 | 1 | 1 |
| 1 | 1 | |
| 1 | 1 | |
3) Логическое отрицание или инверсия:
Инверсия — это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.
Таблица истинности для инверсии
| A | неА |
| 1 | |
| 1 |
4) Логическое следование или импликация:
Импликация — это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. Тоесть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.
Таблица истинности для импликации
| A | B | F |
| 1 | 1 | 1 |
| 1 | ||
| 1 | 1 | |
| 1 |
document.write(showadvertisement_2());
5) Логическая равнозначность или эквивалентность:
Эквивалентность — это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.
Таблица истинности для эквивалентности
| A | B | F |
| 1 | 1 | 1 |
| 1 | ||
| 1 | ||
| 1 |
Порядок выполнения логических операций в сложном логическом выражении
1. Инверсия;
2. Конъюнкция;
3. Дизъюнкция;
4. Импликация;
5. Эквивалентность.
Для изменения указанного порядка выполнения логических операций используются скобки.
Логические выражения и таблица истинности
Таблица истинности — таблица, показывающая, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний.
Логическое выражение — составные высказывания в виде формулы.
Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак «=».
Алгоритм построения таблицы истинности:
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 столбцов.
Онлайн калькулятор позволяет быстро строить таблицу истинности для произвольной булевой функции или её вектора, рассчитывать совершенную дизъюнктивную и совершенную конъюнктивную нормальные формы, находить представление функции в виде полинома Жегалкина, строить карту Карно и классифицировать функцию по классам Поста.
Калькулятор таблицы истинности, СКНФ, СДНФ, полинома Жегалкина
введите функцию или её вектор
Построено таблиц, форм: 9014
Как пользоваться калькулятором
- Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)
- Укажите действия, которые необходимо выполнить с помощью переключателей
- Укажите, требуется ли вывод решения переключателем "С решением"
- Нажмите на кнопку "Построить"
Видеоинструкция к калькулятору
Используемые символы
В качестве переменных используются буквы латинского и русского алфавитов (большие и маленькие), а также цифры, написанные после буквы (индекс переменной). Таким образом, именами переменных будут: 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
- Выписать простые конъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 0, то она входит в конъюнкцию с отрицанием, а иначе без отрицания
- Объединить все простые конъюнкции с помощью дизъюнкции
Алгоритм построения СКНФ для булевой функции
- Построить таблицу истинности для функции
- Найти все наборы аргументов, на которых функция принимает значение 0
- Выписать простые дизъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 1, то она входит в дизъюнкцию с отрицанием, а иначе без отрицания
- Объединить все простые дизъюнкции с помощью конъюнкции
Алгоритм построения полинома Жегалкина булевой функции
Есть несколько методов построения полинома Жегалкина, в данной статье рассмотрим наиболее удобный и простой из всех.
- Построить таблицу истинности для функции
- Добавить новый столбец к таблице истинности и записать в 1, 3, 5. ячейки значения из тех же строк предыдущего столбца таблицы истинности, а к значениям в строках 2, 4, 6. прибавить по модулю два значения из соответственно 1, 3, 5. строк.
- Добавить новый столбец к таблице истинности и переписать в новый столбец значения 1, 2, 5, 6, 9, 10. строк, а к 3, 4, 7, 8, 11, 12. строкам аналогично предыдущему пункту прибавить переписанные значения.
- Повторить действия каждый раз увеличивая в два раза количество переносимых и складываемых элементов до тех пор, пока длина не станет равна числу строк таблицы.
- Выписать булевы наборы, на которых значение последнего столбца равно единице
- Записать вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора записать единицу) и объединить их с помощью операции исключающего ИЛИ.
Примеры построения различных представлений логических функций
Построим совершенные дизъюнктивную и дизъюнктивную нормальные формы, а также полином Жегалкина для функции трёх переменных 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 — позвольте нам писать код для вас и вы получите качественное решение в короткие сроки по привлекательной цене!