Таблицы истинности примеры с решениями

Докажите, что А В равносильно (A\/ ¬B) /\ (¬A\/ B)

Для доказательства равносильности двух высказываний достаточно построить таблицу истинности для высказывания (A\/ ) /\ (\/ B) и сравнить ее с таблицей истинности эквивалентности:

¬AVB

(A\/¬B) /\ (¬A \/B)

Последние столбцы этих функций совпадают, значит, они равносильны. ЧТД.

Укажите, какое логическое выражение равносильно выражению

A /\ ¬ (¬B \/ C)

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

Определите истинность следующего высказывания: «За окном светит солнце, и нет дождя».

Нам дано сложное составное высказывание. Выделим из него простые высказывания:

А = «За окном светит солнце»

Составим логическую функцию, соответствующую данному высказыванию.

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

¬B

A /\ ¬B

Ответ: логическое выражение принимает значение истина только при наборе F(1,0)=1.Следовательно, данное нам высказывание истинно только тогда, когда первое простое высказывание истинно, а второе ложно.

Определите истинность следующего высказывания: «Гости смеялись, шутили и не расходились по домам».

Выделим из данного сложного высказывания простые высказывания:

С = «Гости расходились по домам»

Составим логическую функцию, соответствующую данному высказыванию.

Построим таблицу истинности для данной логической функции.

¬C

A /\ B/\¬C

Ответ: логическое выражение принимает значение истина только при наборе F(1,1,0)=1.Следовательно, данное нам высказывание истинно только тогда, когда первое и второе простые высказывания истинны, а второе ложно.

На языке алгебры логики составьте истинное тождество, соответствующее заданному условию задачи:

Школьника, Миша, остававшийся в классе на перемене, был вызван к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчик ответили следующее: «Я не бил окно, и Коля тоже…»

Известно, что он либо сказал чистую правду, либо в одной части заявления соврал, а другое его высказывание истинно, либо оба факта исказил.

Если Миша сказал чистую правду, то¬ А /\ ¬ В = 1.

Если в одной части заявления Миша соврал, а другое его высказывание истинно, то (¬А /\ В) \/ (А /\¬В) = 1

Если Миша оба факта исказил, то А /\ В = 1.

Истинное тождество, соответствующее условию задачи будет выглядеть так: ¬А /\ ¬В \/¬А /\ В \/А /\ ¬ В \/ А /\ В = 1.

источник

Они могут принимать значения «истина» или «ложь» (1 или 0). Для функции, содержащей две переменные, наборов значений переменных всего четыре:

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

1. Конъюнкция (логическое умножение) – сложное логическое выражение, которое является истинным только в том случае, когда истинны оба входящих в него простых выражения.

Обозначение:

2. Дизъюнкция (логическое сложение) – это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно, если оба простых логических выражения ложны.

Обозначение:

3. Импликация (логическое следствие) – это сложное логическое выражение, которое является ложным тогда и только тогда, когда условие истинно, а следствие ложно.

Обозначение:

4. Эквиваленция – это сложное логическое высказывание, которое является истинным только при одинаковых значениях истинности простых выражений, входящих в него.

Обозначение:

5. Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное – истинным.

Обозначение:

6. Штрих Шеффера – операция, отрицающая конъюнкцию, т.е. значение ложно тогда и только тогда, когда оба простых выражения истинны.

Обозначение:

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

Обозначение:

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

Инверсия
Конъюнкция
Дизъюнкция
Импликация
Эквиваленция
Штрих Шеффера
Стрелка Пирса

Для последних двух операций приоритет не определен.

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

Задание

Составить таблицу истинности для функции

Решение

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

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

Решение Составим таблицу истинности для заданной функции, которая содержит три переменные

. Наборов возможных переменных будет 8 и запишем их в первых трех столбцах таблицы, в последующих столбцах — значения промежуточных функций и в последнем столбце — значение функций.

I –

II –

III –

IV –

V –

VI –

источник

Логическая функция – функция, переменные которой принимают одно из двух значений: $1$ или $0$.

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

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

Равносильными называются логические выражения, последние столбцы таблиц истинности которых совпадают. Равносильность обозначается с помощью знака $«=»$.

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

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

Определяют количество строк: кол-во строк = $2^n + 1$ (для строки заголовка), $n$ – количество простых выражений. Например, для функций двух переменных существует $2^2 = 4$ комбинации наборов значений переменных, для функций трех переменных – $2^3 = 8$ и т.д.

Определяют количество столбцов: кол-во столбцов = кол-во переменных + кол-во логических операций. При определении количества логических операций учитывают также порядок их выполнения.

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

Попробуй обратиться за помощью к преподавателям

Составить таблицу истинности логического выражения $D=\bar \vee (B \vee C)$.

Определим количество строк:

Количество простых выражений – $n=3$, значит

Определим количество столбцов:

Количество логических операций и их последовательность:

Заполним таблицу, учитывая таблицы истинности логических операций.

Задай вопрос специалистам и получи
ответ уже через 15 минут!

По данному логическому выражению построить таблицу истинности:

Определим количество строк:

Количество простых выражений – $n=3$, значит

Определим количество столбцов:

Количество логических операций и их последовательность:

отрицание ($\bar$);
дизъюнкция, т.к. она находится в скобках ($A \vee B$);
конъюнкция ($(A\vee B)\bigwedge \overline$);
отрицание, которое обозначим $F_1$ ($\overline<(A\vee B)\bigwedge \overline>$);
дизъюнкция ($A \vee C$);
конъюнкция ($(A\vee C)\bigwedge B$);
отрицание, которое обозначим $F_2$ ($\overline<(A\vee C)\bigwedge B>$);

Заполним таблицу, учитывая таблицу истинности логических операций.

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

По данной таблице истинности некоторой логической функции $Y(A,B)$ cоставить соответствующую логическую функцию.

Значение функции равно $1$ в $1$-й и $3$-й строках таблицы.
Поскольку имеем $2$ строки, получим дизъюнкцию двух элементов:

Каждое логическое выражение в этой дизъюнкции запишем как конъюнкцию аргументов функции $A$ и $B$: $\left(A\wedge B\right)\vee \left(A\wedge B\right)$

В случае, когда значение в соответствующей строке таблицы равно $0$, запишем этот аргумент с отрицанием, получим искомую функцию:\[Y\left(A,B\right)=\left(\overline\wedge \overline\right)\vee \left(A\wedge \overline\right).\]

Так и не нашли ответ
на свой вопрос?

Просто напиши с чем тебе
нужна помощь

источник

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

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

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

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

Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)

Укажите действия, которые необходимо выполнить с помощью переключателей

Укажите, требуется ли вывод решения переключателем “С решением”

Нажмите на кнопку “Построить”

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

Для записи логических операций можно использовать как обычные символы клавиатуры ( * , + , ! , ^ , -> , = ), так и символы, устоявшиеся в литературе ( ∧ , ∨ , ¬ , ⊕ , → , ≡ ). Если на вашей клавиатуре отсутствует нужный символ операции, то используйте клавиатуру калькулятора (если она не видна, нажмите “Показать клавиатуру”), в которой доступны как все логические операции, так и набор наиболее часто используемых переменных.

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

Строить таблицу истинности по функции

Строить таблицу истинности по двоичному вектору

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

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

Строить полином Жегалкина (методами Паскаля, треугольника, неопределённых коэффициентов)

Определять принадлежность функции к каждому из пяти классов Поста

Строить карту Карно

Минимизировать ДНФ и КНФ

Искать фиктивные переменные

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

Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения более простых. В качестве основных операций обычно называют конъюнкцию (∧ или &), дизъюнкцию (∨ или |), импликацию (→), отрицание (¬), эквивалентность (=), исключающее ИЛИ (⊕).

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 — мы с радостью поможем с этим!

В том числе мы занимаемся репетиторством по информатике и программированию, а также готовим к ОГЭ и ЕГЭ!

Более 750 выполненных заказов;

Более 100 отзывов;

Качественное решение

Короткие сроки и привлекательные цены

Различные акции и скидки

Programforyou — позвольте нам писать код для вас и вы получите качественное решение в короткие сроки по привлекательной цене!

источник

№1 Постройте таблицы истинности для следующих выражений:

9) ¬( x∧y∧z ); 10) ¬(x∧¬y∧z); 11) ¬(x∨y∨z); 12) ¬( x∨¬y∨z).

А. В задачах 1) – 4) выражение – это конъюнкция переменных или их отрицаний. Такие выражения принимают значение 1 только при одном наборе переменных. В этом наборе переменная принимает значение 1, если в выражение она входит без отрицания и 0 в противном случае. Таблицы истинности приведены ниже.

y x ∧ y ∧ z y x ∧ y ∧ z

1 1

1 1 1

y x ∧ ¬y ∧ z y x ∧ ¬y ∧ z

1

1 1 1 1

1 1 1

1 1 1 1 1

y x ∧ y ∧ ¬z y x ∧ y ∧ ¬z

1

1 1 1

1 1 1

y ¬x∧ ¬y∧¬z y ¬x∧ ¬y∧¬z

1

1

1 1

1 1 1

Б. В задачах 5) – 8) выражение – это дизъюнкция переменных или их отрицаний. Такие выражения принимают значение 0 только при одном наборе переменных. В этом наборе переменная принимает значение 1, если в выражение она входит с отрицанием и 0 в противном случае. Таблицы истинности приведены ниже.

y x ∨ y ∨ z y x ∨ y ∨ z

1

1 1 1

1 1 1 1

1 1 1 1 1

y x ∨ ¬y∨z y x ∨ ¬y∨z

1 1

1 1 1

1 1 1

1 1 1 1 1

y x∨y∨¬z y x∨y∨¬z

1 1

1 1

1 1 1 1

1 1 1 1 1

y ¬x∨¬y∨¬z y ¬x∨¬y∨¬z

1 1

1 1 1

1 1 1 1

1 1 1 1

В. В задачах 9) – 12) выражение – это отрицание конъюнкции или дизъюнкции. При построении таблицы истинности можно воспользоваться правилами А и Б, заменив потом значения выражения на противоположные.

y ¬(x∧y∧z) y ¬(x∧y∧z)

1 1

1 1 1

1 1 1 1

1 1 1 1

y ¬(x∧¬y∧z) y ¬(x∧¬y∧z)

1 1

1 1

1 1 1 1

1 1 1 1 1

y ¬(x∨y∨z) y ¬(x∨y∨z)

1

1

1 1

1 1 1

y ¬(x∨¬y∨z) y ¬(x∨¬y∨z)

1

1 1 1

1 1 1

№2 Постройте таблицы истинности для следующих выражений:

Укажите, для каких выражений таблицы истинности совпадают.

Построим соответствующие таблицы истинности.

y 1

1 1

1

1 1 1

y 1

1

1 1

1 1 1

y 1

1 1

1

1 1 1

y 1

1 1

1

1 1 1

y

1 1

1 1

1 1 1

y 1

1 1

1 1

1 1

y 1

1

1 1

1 1 1

y 1

1

1 1

1 1 1

Одинаковые таблицы истинности – это таблицы, в которых одинаковому набору значений переменных и выражения в одной соответствует одинаковые в другой.

Тогда сравнив все таблицы, имеем совпадающие: 1-3-8, 2-4-7.

№3 Постройте таблицы истинности для следующих выражений:

1) (x → y) → z; 2) x → (y → z); 3) ( ¬x → y) → z; 4) ¬x → (y → z);

5) (x → y) → ¬z; 6) x → (y → ¬z); 7) ( ¬x → y) → ¬z; 8) ¬x → (y → ¬z).

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

Для решения этих задач нужно знать определение истинности импликации: через связь с дизъюнкцией

или непосредственно через таблицу истинности:

y 1

1 1

1

1 1 1

При построении таблицы истинности для конкретного выражения удобно сначала выписать все 8 возможных наборов значений аргументов, а затем по очереди вычислять значение выражения для каждого набора. При желании можно использовать вспомогательную таблицу, в которой будет дополнительный столбец для подвыражения (см. №№ 9 и 10 ниже). Например, для задачи 3.1 вспомогательная таблица будет выглядеть так:

y x → y x z (x → y) → z

1 1 1

1 1 1 1 1 1

1 1 1 1 1

1 1 1 1 1 1 1 1 1

Ниже приведены ответы для всех выражений.

y (x → y) → z y (x → y) → z

1 1

1 1 1 1 1

1 1 1

1 1 1 1 1 1 1

Посмотрев на таблицу истинности, получим, что истинных наборов: 5.

y x → (y → z) y x → (y → z)

1 1 1

1 1 1 1 1

1 1 1 1

1 1 1 1 1 1 1

Посмотрев на таблицу истинности, получим, что истинных наборов: 7.

y ( ¬x → y) → z y ( ¬x → y) → z

1 1

1 1 1 1 1

1 1 1

1 1 1 1 1 1 1

Посмотрев на таблицу истинности, получим, что истинных наборов: 5.

y ¬x →(y →z) y ¬x → (y →z)

1 1 1

1 1 1 1 1

1 1 1 1

1 1 1 1 1 1 1

Посмотрев на таблицу истинности, получим, что истинных наборов: 7.

y (x →y) →¬z y (x →y) → ¬z

1 1 1

1 1 1 1

1 1 1 1 1

1 1 1 1 1

Посмотрев на таблицу истинности, получим, что истинных наборов: 5.

y x → (y→¬z) y x → (y →¬z)

1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1 1

Посмотрев на таблицу истинности, получим, что истинных наборов: 7.

y (¬x→y)→¬z y (¬x→y)→¬z

1 1 1

1 1 1 1

1 1 1 1 1

1 1 1 1 1

Посмотрев на таблицу истинности, получим, что истинных наборов: 5.

y ¬x→(y→¬z) y ¬x→(y→¬z)

1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1 1

Посмотрев на таблицу истинности, получим, что истинных наборов: 7.

№4 Разбейте эти выражения на группы так, чтобы выражения, попавшие а одну группу имели одинаковые таблицы истинности, а выражения, попавшие в разные группы, – разные таблицы истинности.

1) x → (y → z); 2) ¬x → (y → z); 3) x → ( ¬y → z); 4) x → (y → ¬z);

5) x ∨ y ∨ z; 6) ¬x ∨ y ∨ z; 7) x ∨ ¬y ∨ z; 8) x ∨ y ∨ ¬z;

9) ¬x ∨ ¬y ∨ z; 10) x ∨ ¬y ∨ ¬z; 11) ¬x ∨ y ∨ ¬z; 12) ¬x ∨ ¬y ∨ ¬z.

Укажите, для каких выражений таблицы истинности совпадают.

Задачу можно решить двумя способами. Один способ – построить таблицы истинности для всех выражений и посмотреть, какие таблицы совпадают (см. ниже Решение Б). Этот способ простой по идее, но трудоемкий. Есть и другое решение, требующее меньше вычислений (см. Решение А).

Решение А. Выражения 5) – 12) – элементарные дизъюнкции, т.е. дизъюнкции простых переменных или их отрицаний. Два разных выражения такого вида не могут быть эквивалентными, т.е. иметь одинаковые таблицы истинности, см. решение задачи 1, пп. 5- 8. Выражения 1) – 4) тоже могут быть записаны в виде элементарных дизъюнкций, см. решения задач №№2 и 3. Поэтому для решения задачи достаточно записать каждое из выражений 1) – 4) в виде элементарной дизъюнкции и посмотреть, не совпадает ли эта дизъюнкция с одной из дизъюнкций 5) – 12).

x→ (y → z) = ¬x ∨ (y → z) = ¬x ∨ (¬y∨z) = ¬x ∨ ¬y ∨ z – это выражение 9).
¬x→ (y → z) = x ∨ (y → z) = x ∨ (¬y∨z) = x ∨ ¬y ∨ z – это выражение 7).
x→ (¬y → z) = ¬x ∨ (¬y → z) = ¬x ∨ (y∨z) = ¬x ∨ y ∨ z – это выражение 6).
x→ (y → ¬z) = ¬x ∨ (y → ¬z) = ¬x ∨ (¬y∨¬z) = ¬x ∨ ¬y ∨ ¬z – это выражение 12).

Ответ. Таблицы истинности совпадают для выражений 1 и 9, 2 и 7, 3 и 6, 4 и 12. Для выражений 5, 8, 10 и 11 нет других выражений с той же таблицей истинности.

Построим соответствующие таблицы истинности.

y x → (y → z) y x→(y→z)

1 1 1

1 1 1 1 1

1 1 1 1

1 1 1 1 1 1 1

y ¬x →(y→ z) y ¬x→(y → z)

1 1 1

1 1 1 1 1

1 1 1 1

1 1 1 1 1 1 1

y x→( ¬y→ z) y x→( ¬y→ z)

1

1 1

1 1 1 1

1 1 1 1

y x→(y →¬z) y x →(y →¬z)

1 1

1 1

1 1 1 1

1 1 1

y x ∨ y ∨ z y x ∨ y ∨ z

1

1 1

1 1 1 1

1 1 1 1

y ¬x ∨ y ∨ z y ¬x ∨ y ∨ z

1

1 1

1 1 1 1

1 1 1 1

y x ∨ ¬y ∨ z y x ∨ ¬y ∨ z

1 1

1 1

1 1 1

1 1 1 1

y x ∨ y ∨ ¬z y x ∨ y ∨ ¬z

1 1

1

1 1 1 1

1 1 1 1

y ¬x ∨¬y ∨ z y ¬x ∨¬y ∨ z

1 1

1 1

1 1 1

1 1 1 1

y x ∨¬y ∨ ¬z y x ∨¬y ∨ ¬z

1 1

1 1

1 1 1 1

1 1 1

y ¬x ∨ y ∨¬z y ¬x ∨ y ∨¬z

1 1

1

1 1 1 1

1 1 1 1

y ¬x∨¬y∨¬z y ¬x∨¬y ∨¬z

1 1

1 1

1 1 1 1

1 1 1

Одинаковые таблицы истинности – это таблицы, в которых одинаковому набору значений переменных и выражения в одной соответствует одинаковые в другой.

Тогда сравнив все таблицы, имеем совпадающие: 1-9, 2-7, 3-6, 4-12.

Ответ. Таблицы истинности совпадают для выражений 1 и 9, 2 и 7, 3 и 6, 4 и 12. Для выражений 5, 8, 10 и 11 нет других выражений с той же таблицей истинности

№5 Для каждого из следующих выражений постройте выражение с такой же таблицей истинности и содержащее только связки → (импликация) и ¬ (отрицание):

1) x ∨ y ∨ z; 2) ¬x ∨ y ∨ z; 3) x ∨ ¬y ∨ z 4) x ∨ y ∨ ¬z;

5) ¬x ∨ ¬y ∨ z; 6) x ∨ ¬y ∨ ¬z; 7) ¬x ∨ y ∨ ¬z 8) ¬x ∨ ¬y ∨ ¬z.

Решение этой задачи основано на тождестве

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

1) x ∨ y ∨ z = ¬x → (y ∨ z) = ¬x → ( ¬y → z)

y ¬x→(¬y→z) y ¬x→(¬y→z)

1

1 1

1 1 1 1

1 1 1 1

2) ¬x ∨ y ∨ z = x → (y ∨ z) = x → ( ¬y → z)

y x →(¬y →z) y x →(¬y →z)

1

1 1

1 1 1 1

1 1 1 1

3) x ∨ ¬y ∨ z = ¬x → (¬y ∨ z) = ¬x → (y → z)

y ¬x→(y →z) y ¬x→(y →z)

1 1

1 1

1 1 1

1 1 1 1

4) x ∨ y ∨ ¬z = ¬x → (y ∨ ¬z) = ¬x → ( ¬y → ¬z)

y ¬x→(¬y→¬z) y ¬x→(¬y→¬z)

1 1

1

1 1 1 1

1 1 1 1

5) ¬x ∨ ¬y ∨ z = x → (¬y ∨ z) = x → (y → z)

y x→(y→z) y x→(y→z)

1 1

1 1

1 1 1

1 1 1 1

6) x ∨ ¬y ∨ ¬z = ¬x → (¬y ∨ ¬z) = ¬x → (y → ¬z)

y ¬x→(y→¬z) y ¬x→(y→¬z)

1 1

1 1

1 1 1 1

1 1 1

7) ¬x ∨ y ∨ ¬z = x → (y ∨ ¬z) = x → ( ¬y → ¬z)

y x→(¬y→¬z) y x→(¬y→¬z)

1 1

1

1 1 1 1

1 1 1 1

8) ¬x ∨ ¬y ∨ ¬z = x → (¬y ∨ ¬z) = x → (y → ¬z)

y x →(y→¬z) y x →(y→¬z)

1 1

1 1

1 1 1 1

1 1 1

№6. Для каждого из следующих выражений постройте выражение с такой же таблицей истинности и содержащее только связки → (импликация) и ¬ (отрицание):

1) ¬(x ∨ y) ∨ z; 2) ¬(x ∧ y) ∨ z; 3) x ∨ ¬(y ∨ z); 4) ¬(x ∨ y ∨ z);

5) ¬(x ∨ ¬y) ∨ z; 6) ¬(¬x ∧ ¬y) ∨ z; 7) ¬x ∨ ¬(¬y ∨ z); 8) ¬(x ∨ y ∨ ¬z).

этой задачи основано на тождестве

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

1) ¬(x ∨ y) ∨ z = (x ∨ y) → z = (¬x → y) → z

y (¬x→y)→z y (¬x→y)→z

1

1 1

1 1

1 1 1 1

Здесь требуется применить закон Де Моргана:

¬(x ∧ y) ∨ z = ¬x ∨¬y ∨ z = (x →¬y) ∨ z = ¬(x →¬y) → z

y ¬(x→¬y)→z y ¬(x→¬y)→z

1 1

1 1

1 1 1

1 1 1 1

3) x ∨ ¬(y ∨ z) = ¬(y ∨ z) ∨ x = (y ∨ z) → x = (¬y → z) → x

y x ∨ ¬(y ∨ z) y x ∨ ¬(y ∨ z)

1 1

1

1 1 1

1 1 1

4) ¬(x ∨ y ∨ z) = ¬((¬x → y) ∨ z) = ¬(¬(¬x → y) → z)

y ¬(¬(¬x→y)→z) y ¬(¬(¬x→y)→z)

1

1 1

1 1

5) ¬(x ∨ ¬y) ∨ z = (x ∨ ¬y) → z = (¬y ∨ x) → z = (y → x) → z

y (y → x) → z y (y → x) → z

1 1

1 1 1

1 1 1 1

Здесь требуется применить закон Де Моргана:

¬(¬x ∧ ¬y) ∨ z = x ∨ y ∨ z = (¬x→y) ∨ z = ¬(¬x→y) → z

y ¬(¬x→y)→z y ¬(¬x→y)→z

1

1 1

1 1 1 1

1 1 1 1

7) ¬x ∨ ¬(¬y ∨ z) = ¬(¬y ∨ z) ∨ ¬x = (¬y ∨ z) → ¬x = (y → z) → ¬x

y (y→z)→¬x y (y→z)→¬x

1

1

1 1 1 1

1 1 1

8) ¬(x ∨ y ∨ ¬z) = ¬((¬x→y) ∨ ¬z) = ¬(¬z ∨ (¬x→y)) = ¬(¬z → (¬x→y))

y ¬(¬z→ (¬x→y)) y ¬(¬z→ (¬x→y))

1

1 1

1 1

№7. Для каждого из следующих выражений постройте выражение с такой же таблицей истинности и содержащее только связки → (импликация) и ¬ (отрицание):

1) ¬x ∧ ¬y ∧ z; 2) ¬x ∨ y ∧ ¬z; 3) x ∨ y ∨ z; 4) ¬x ∧ y ∨ z;

5) ¬ x ∧ ¬y ∧ ¬z; 6) x ∨ ¬y ∧ ¬z; 7) ¬x ∨ ¬y ∨ z; 8) ¬x ∧ ¬y ∨ z.

Здесь требуется применить закон Де Моргана:

¬x ∧ ¬y ∧ z = ¬(x ∨ y) ∧ z = ¬(¬(x ∨ y) ∨ ¬z) = ¬((x ∨ y) → ¬z) = ¬((¬x → y) → ¬z)

y ¬((¬x→y)→¬z) y ¬((¬x→y)→¬z)

1

1 1

1 1

Здесь требуется применить закон Де Моргана:

¬x ∨ y ∧ ¬z = ¬x ∨ ¬(¬y ∨ z) = x → ¬(y → z)

y x→¬(y→z) y x→¬(y→z)

1

1

1 1 1 1

1 1 1

3) x ∨ y ∨ z = (¬x → y) ∨ z = (¬x → y) → z

y (¬x→y)→z y (¬x→y)→z

1

1 1

1 1 1 1

1 1 1 1

Здесь требуется применить закон Де Моргана:

¬x ∧ y ∨ z = ¬(x ∨ ¬y) ∨ z = (x ∨ ¬y) → z = (¬y ∨ x) → z = (y → x) → z

y (y → x) → z y (y → x) → z

1 1

1 1 1

1 1 1 1

Здесь требуется применить закон Де Моргана:

¬x ∧ ¬y ∧ ¬z = ¬(x ∨ y ) ∧ ¬z = ¬((x ∨ y) ∨ z) = ¬((¬x → y) ∨ z) = ¬(¬(¬x→y)→z)

y ¬(¬(¬x→y)→z) y ¬(¬(¬x→y)→z)

1

1 1

1 1

Здесь требуется применить закон Де Моргана:

x ∨ ¬y ∧ ¬z = x ∨ ¬(y ∨ z) = ¬(y ∨ z) ∨ x = (y ∨ z) → x = (¬y → z) → x

y (¬y→z)→x y (¬y→z)→x

1 1

1

1 1 1

1 1 1

7) ¬x ∨ ¬y ∨ z = ¬x ∨ z ∨ ¬y = (x → z) ∨ ¬y = ¬y ∨ (x → z) = y → (x → z)

y y → (x → z) y y → (x → z)

1 1

1 1

1 1 1

1 1 1 1

Здесь требуется применить закон Де Моргана:

¬x ∧ ¬y ∨ z = ¬(x ∨ y) ∨ z = (x ∨ y) → z = (¬x → y) → z

y (¬x →y)→z y (¬x →y)→z

1

1 1

1 1

1 1 1 1

№8. Сравните формулы из задач №6 и №7. Какие из них эквивалентны?

Чтобы преобразовать формулы из задачи №6 к виду из задачи №7 нужно раскрыть скобки. Для этого нужно использовать законы Де Моргана:

После этого находим для каждой формулы из задачи №6 эквивалентную ей формулу в задаче №7. Рассмотрим, например, формулу 1) из задачи №6. Имеем:

Последняя формула – это формула 8) задачи №7

Ответ. Для каждой формулы задачи №6 указана эквивалентная ей формула задачи №7.

1) = 8); 2) = 7); 3) = 6); 4) = 5); 5) = 4); 6) = 3); 7) = 2); 8) = 1)

№9. Постройте таблицу истинности для следующего выражения:

Обозначим выражение через F. Выражение F зависит от трех переменных A, C, D; для них есть 8 наборов возможных значений. Значит, в таблице истинности (кроме строки-заголовка) будет 8 строк. При составлении таблицы истинности удобно выделить подвыражения и сначала построить вспомогательную таблицу, в которой кроме значений выражения F будут и значения подвыражения выражения F. Для этого выделим в выражении F его подвыражения.

1) Выражение F можно записать в виде S1 → S2, где

2) Выделяем подвыражения в выражении S2: S2 = S3∨S4, где

3) Продолжаем разбор. Разбираем выражение S3 (выражением S4 займемся позже):

4) Выражение S5 можно записать в виде:

S6 = D∧A (это выражение эквивалентно S1);

6) Это выражение представим следующим образом:

7) Вернемся теперь к разбору выражения S4:

8) Представим выражение S10 как:

S12 = A∧C (это выражение эквивалентно S9).

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

12 10 9 7 4 2 13

C S1 S3 S5 S7 S9 S11 F

1 1

1 1

1 1 1

1 1 1 1

1 1

1

1 1 1 1 1

1 1 1 1

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

C D∧A→(A∧D⇔¬(D∨A∧C))∧A∨¬(D∧C→A∧C)

1

1

1 1

1 1

1

1 1

1

№10. Постройте таблицу истинности для следующего выражения:

Обозначим выражение через F. Выражение F зависит от трех переменных A, C, D; для них есть 8 наборов возможных значений. Значит, в таблице истинности (кроме строки-заголовка) будет 8 строк. При составлении таблицы истинности удобно выделить подвыражения и сначала построить вспомогательную таблицу, в которой кроме значений выражения F будут и значения подвыражения выражения F.

1) Выражение F можно записать в виде S1 ⇔ S2, где

2) Продолжим с разбора выражения S1. Его можно представить в виде S1 = C ∨ S3, где

3) Выделим подвыражения S4 и S5 из S3: S3 = S4 → S5, где

4) Выражение S4 можно представить следующим образом соответственно:

5) Аналогично рассмотрим выражение S5: S5 = ¬S8, где

6) Теперь рассмотрим выражение S2: S2 = S10 → S11, где

7) Выражение S10 представим в виде: S10 = S12 ∨ A, где

8) Выражение S11: S11 = ¬S13, где

S13 = D ∧ C (это выражение эквивалентно S9).

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

13 11 9 7 5 3 1 A D S2 S4 S6 S8 S10 S12 F

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

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

C C∨(A∧¬(D∧A)→¬(A∨D∧C))⇔A∧C∨A→¬(D∧C)

1

1

1 1

1 1

1

1 1

1

№11. Постройте таблицу истинности для следующего выражения:

Обозначим выражение через F. Выражение F зависит от трех переменных A, C, D; для них есть 8 наборов возможных значений. Значит, в таблице истинности (кроме строки-заголовка) будет 8 строк. При составлении таблицы истинности удобно выделить подвыражения и сначала построить вспомогательную таблицу, в которой кроме значений выражения F будут и значения подвыражения выражения F.

1) Выражение F можно записать в виде S1 ∨ S2 ∨ A, где

2) Представим сначала выражение S1 в виде: S1 = ¬S3, где

3) Теперь разобьем на подвыражения S2: S2 = S4 ∧ S5, где

4) Выражение S4 представим в виде: S4 = S6 → S7;

5) Аналогично преобразуем выражение S7: S7 = ¬S8, где

6) Это выражение представим в вид: S8 = S9 ⇔ S10, где

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

10 8 6 4 2 11

C S1 S3 S5 S7 S9 F

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

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

источник

Читайте также: В какой горшок сажать фикус

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

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

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

C	D∧A→(A∧D⇔¬(D∨A∧C))∧A∨¬(D∧C→A∧C)
	1
	1
1	1
1	1
	1

1	1
1

C	C∨(A∧¬(D∧A)→¬(A∨D∧C))⇔A∧C∨A→¬(D∧C)
	1
	1
1	1
1	1

	1
1	1
1