Решить логическое уравнение используя таблицу истинности

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

Содержание:

Построение таблиц истинности для логических выражений

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

1. подсчитать п — число переменных в выражении;
2. подсчитать общее число логических операций в выражении;
3. установить последовательность выполнения логических операций с учётом скобок и приоритетов;
4. определить число столбцов в таблице: число переменных + число операций;
5. заполнить шапку таблицы, включив в неё переменные и операции в соответствии с последовательностью, установленной в п. 3;
6. определить число строк в таблице (не считая шапки таблицы): ;
7. выписать наборы входных переменных с учётом того, что они представляют собой ряд целых п-разрядных двоичных чисел от 0 до ;
8. провести заполнение таблицы по столбцам, выполняя логические операции в соответствии с установленной последовательностью.

Построим таблицу истинности для логического выражения нём две переменные, две операции, причём сначала выполняется конъюнкция, а затем — дизъюнкция. Всего в таблице будет четыре столбца:

• Наборы входных переменных — это целые числа от 0 до 3, представленные в двухразрядном двоичном коде: 00, 01, 10, 11.

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

Заполненная таблица истинности имеет вид:

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

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

Свойства логических операций

Рассмотрим основные свойства логических операций, называемые также законами алгебры логики.

1. Переместительный (коммутативный) закон:

• для логического умножения:

• для логического сложения:

2. Сочетательный (ассоциативный) закон:

• для логического умножения:

• для логического сложения:

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

3. Распределительный (дистрибутивный) закон:

• для логического умножения:

• для логического сложения:

4. Закон двойного отрицания:

Двойное отрицание исключает отрицание.

5. Закон исключённого третьего:

• для логического умножения:

• для логического сложения:

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

6. Закон повторения:

• для логического умножения:

• для логического сложения:

7. Законы операций с 0 и 1:

• для логического умножения:

• для логического сложения:

8. Законы общей инверсии:

• для логического умножения:

• для логического сложения:

Законы алгебры логики могут быть доказаны с помощью таблиц истинности

Докажем распределительный закон для логического сложения:

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

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

Пример 1.

Найдём значение логического выражения для числа X = 0.

Решение:

При X = 0 получаем следующее логическое выражение: . Так как логические выражения 0

Для решения задач вам понадобится знание таблиц истинности логических операций:

А также, вы должны знать:

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

Сначала выполняется операция отрицания НЕ

после И выполняется ИЛИ

и в последнюю очередь — эквивалентность.

Задача 1

Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

Решение:

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

То выражение, значения которого совпадут со значениями столбца F, и будет искомым. Решение:

Задача 2

Дан фрагмент таблицы истинности выражения F:

Каким выражением может быть F?

Решение:

1) В каждом из приведенных выражений логические переменные связывает только один тип логической операции. В 1 и 3 вариантах это операция И (), во 2 и 4 вариантах это операция ИЛИ ().

2) По столбцу F видно, что выражение для двух комбинаций данных истинно, а для одной — ложно. Следовательно, выражение не может быть логическим умножением (И), так как логическое умножение истинно только для одной комбинации данных, а в таблице две истины. Следовательно, искомое выражение является логическим сложением (ИЛИ) значений логических переменных.

Поэтому, в качестве ответа может быть 2 или 4 вариант. Рассмотрим их.

1) 2-й вариант: В первой строке таблицы истинности отображены только значения х1, хЗ, х5, и все они равны 0. Но в формуле 2го варианта у нас х5 отрицается, то есть значение х5 будет изменено на 1, и в результате всё выражение должно быть истинным. Что не соответствует заданной таблице. Остаётся 4-й вариант.

2) Как мы видим, переменные х1, хЗ и х5 в 4-м варианте ответа не отрицаются, что соответствует первой строке заданной таблицы.

Задача 4

Какое из приведенных имен сказочных героев удовлетворяет логическому условию:

Решение:

Составим для каждого из предложенных ответов схему соответственно заданной логической формуле. Ищем истинное значение.

Первая буква согласная — НЕТ (0)

Вторая буква не А — ДА (1)

Последняя буква гласная — НЕТ (0) \ / \ у

Предпоследняя буква гласная — ДА (1) X» ‘»X X»

Подставляем полученные значения в формулу и решаем ее: н 0 ->1 ) л 0 -> 1 ),= О

И так с каждым вариантом ответа, пока не найдете истину.

Задача 5

Логическая функция F задаётся выражением

Определите, какому столбцу таблицы истинности функции F соответствует каждая из

переменных X, Y, Z

Решение 1:

Последней операцией выполнения является операция . Поэтому выражение имеет значение ИСТИНА, когда

Рассмотрим все случаи, когда F = 1 (это значения в строках 1 и 3): — не рассматриваем, т.к. в табл, нет строки, где все значения логических переменных = 1.

Рассматриваем только 1 и 3 строки таблицы:

• две единицы в 3-м столбце => это значения X
• два нуля в 1-м столбце => это значения Y
• ноль единица во 2-м столбце => это значения Z

Решение 2:

Последней операцией выполнения является операция . Поэтому выражение

имеет значение ИСТИНА, когда

Выражение F равно 1 в 1й и Зй строках, в этих же строках только “Перем.3”=1, следовательно, значение X находится в 3-м столбце.

Теперь рассмотрим построчно значения 1-х двух столбцов:

(помним, что 1 -> 0 = 0, в остальных комбинациях =1)

1 строка: 0 и О, Y = Z. Поэтому Y и Z для столбцов не определить.

2 строка: 0 и 1. Независимо будет ли Y=0 Z=1 или Y=1 Z=0, функция F=0 т.к. уже

Х=0. Поэтому Y и Z для столбцов не определить.

3 строка: 0 и 1. В этой строке функция F=1, значит Комбинация

невозможна, иначе F будет = 0. Комбинация то, что надо. Следовательно, значение Y находится в 1-м столбце а значение Z во 2-м.

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

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

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

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

Решить логическое уравнение используя таблицу истинности

2) Логическое сложение или дизъюнкция:

Дизъюнкция — это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выраженbя ложны.
Обозначение: F = A v B.

Таблица истинности для дизъюнкции

3) Логическое отрицание или инверсия:

Инверсия — это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.

Обозначение: F = ¬ A.

Таблица истинности для инверсии

4) Логическое следование или импликация:

Импликация — это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.

«A → B» истинно, если из А может следовать B.

Обозначение: F = A → B.

Таблица истинности для импликации

5) Логическая равнозначность или эквивалентность:

Эквивалентность — это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.

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

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

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

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

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

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

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