Составьте таблицу истинности для следующего выражения

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

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

Алгебраические преобразования логических выражений

Любое логическое выражение, как и его переменные (утверждения), принимают два значения: ложь или истина . Ложь обозначается нулём, а истина - единицей. Разобравшись с областью определения и областью допустимых значений, мы можем рассмотреть действия алгебры логики.

Отрицание

Отрицание и инверсия - самое простое логическое преобразование. Ему соответствует частица "не." Это преобразование просто меняет утверждение на противоположное. Соответственно, значение утверждения тоже меняется на противоположное. Если утверждение А истинно, то "не А" - ложно. Например, утверждение "прямой угол - это угол, равный девяносто градусов" - истина. Тогда его отрицание "прямой угол не равен девяноста градусам" - ложь.

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

Дизъюнкция

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

Обычная дизъюнкция или логическое сложение соответствует союзу "или". Она будет истинной если хотя бы одно из утверждений, входящих в неё - истина. Например, выражение "Земля круглая или стоит на трёх китах" будет истинным, так как первое утверждение - истинно, хоть второе и ложно.В таблице это будет выглядеть так:

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

Таблица значений исключающего или

Импликация и эквивалентность

Импликация представляет собой следствие и грамматически может быть выражена как "из А следует Б". Здесь утверждение А будет называться предпосылкой, а Б - следствием. Импликация может быть ложной, только в одном случае: если предпосылка истинна, а следствие ложно. То есть, ложь не может следовать из истины. Во всех остальных случаях импликация истинна. Варианты, когда оба утверждения имеют одинаковую истинность, вопросов не вызывают. Но почему верное следствие из неверной предпосылки - истина? Дело в том, что из ложной предпосылки может следовать что угодно. Это и отличает импликацию от эквивалентности.

В математике (и других доказательных дисциплинах) импликация используется для указания необходимого условия. Например, утверждение А - "точка О - экстремум непрерывной функции", утверждение Б - "производная непрерывной функции в точке О обращается в ноль". Если О, действительно, точка экстремума непрерывной функции, то производная в этой точке будет, и вправду, равна нулю. Если же О не является точкой экстремума, то производная в этой точке может быть нулевой, а может не быть. То есть Б необходимо для А, но не достаточно.

Таблица истинности для импликации выглядит следующим образом:

Логическая операция эквивалентность, по сути, является взаимной импликацией . "А эквивалентно Б" означает, что "из А следует Б" и "из Б следует А" одновременно. Эквивалентность верна, когда оба утверждения либо одновременно верные, либо одновременно неверные.

В математике эквивалентность используется для определения необходимого и достаточного условия. Например, утверждение А - "Точка О является точкой экстремума непрерывной функции", утверждение Б - "В точке О производная функции обращается в ноль и меняет знак". Эти два утверждения эквивалентны. Б содержит необходимое и достаточное условие для А. Обратите внимание, что в данном примере утверждений Б на самом деле является конъюнкцией двух других: "производная в точке О обращается в ноль" и "производная в точке О меняет знак".

Прочие логические функции

Выше были рассмотрены основные логические операции, которые часто используются. Есть и другие функции, которые используются:

Штрих Шеффера или несовместимость представляет собой отрицание конъюнкции А и Б
Стрелка Пирса представляет сбой отрицание дизъюнкции.

Построение таблиц истинности

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

Разбить выражение на простые утверждения и обозначить каждое из них как переменную.
Определить логические преобразования.
Выявить порядок действий этих преобразований.
Сосчитать строки в будущей таблице. Их количество равно два в степени N, где N - число переменных, плюс одна строка для шапки таблицы.
Определить число столбцов. Оно равно сумме количества переменных и количества действий. Можно представлять результат каждого действия в виде новой переменной, если так будет понятней.
Шапка заполняется последовательно, сначала все переменные, потом результаты действий в порядке их выполнения.
Заполнение таблицы надо начать с первой переменной. Для неё количество строк делится пополам. Одна половина заполняется нулями, вторая - единицами.
Для каждой следующей переменной нули и единицы чередуются вдвое чаще.
Таким образом заполняются все столбцы с переменными и для последней переменной значение меняется в каждой строке.
Потом последовательно заполняются результаты всех действий.

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

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

выражения в скобках;
отрицание или инверсия;
конъюнкция;
строгая и обычная дизъюнкция;
импликация;
эквивалентность.

Примеры

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

Штрих Шеффера.
Стрелка Пирса.
Определение эквивалентности.

Штрих Шеффера

Штрих Шеффера - это логическое выражение, которое можно записать в виде "не (А и Б)". Здесь две переменные, и два действия. Конъюнкция в скобках, значит, она выполняется первой. В таблице будет шапка и четыре строки со значениями переменных, а также четыре столбца. Заполним таблицу:

А	Б	А и Б	не (А и Б)
Л	Л	Л	И
Л	И	Л	И
И	Л	Л	И
И	И	И	Л

Отрицание конъюнкции выглядит как дизъюнкция отрицаний. Это можно проверить, если составить таблицу истинности для выражения "не А или не Б". Проделайте это самостоятельно и обратите внимание, что здесь будет уже три операции.

Стрелка Пирса

Рассматривая Стрелку Пирса, которая представляет собой отрицание дизъюнкции "не (А или Б)", сравним её с конъюнкцией отрицаний "не А и не Б". Заполним две таблицы:

А	Б	не А	не Б	не А и не Б
Л	Л	И	И	И
Л	И	И	Л	Л
И	Л	Л	И	И
И	И	Л	Л	Л

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

Определение эквивалентности

Про утверждения А и Б можно сказать, что они эквивалентны, тогда и только тогда, когда из А следует Б и из Б следует А. Запишем это как логическое выражение и построим для него таблицу истинности. "(А эквивалентно Б) эквивалентно (из А следует Б) и (из Б следует А)".

Здесь две переменных и пять действий. Строим таблицу:

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

Основано на: демонстрационных вариантах ЕГЭ по информатике за 2015 год, на учебнике Босовой Людмилы Леонидовны

В предыдущей части 1 мы разобрали с вами логические операции Дизъюнкция и Конъюнкция , нам с вами осталось разобрать инверсию и перейти к решению задания ЕГЭ.

Инверсия

Инверсия — логическая операция, которая каждому высказыванию ста-вит в соответствие новое высказывание, значение которого противопо-ложно исходному.

Для записи инверсии используются следующие знаки: НЕ, `¯` , `¬ `

Инверсия определяется следующей таблицей истинности:

Инверсию иначе называют логическим отрицанием.

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

Логические операции имеют следующий приоритет: инверсия, конъюнк-ция, дизъюнкция.

И так, перед нами задание №2 из ЕГЭ по информатике 2015 года

Александра заполняла таблицу истинности для выражения F. Она успела заполнить лишь небольшой фрагмент таблицы:

x1 x2 x3 x4 x5 x6 x7 x8 F
0 1 0
1 0 1
1 1 1
Каким выражением может быть F?

Значительно облегчает решение задания то, что в каждом варианте сложного выражения F только одна логическая операция: умножение или сложение. В случае умножения /\ если хотя бы одна переменная будет равна нулю, то значение всего выражения F так же должно быть равно нулю. А в случае со сложением V если хотя бы одна переменная будет равна единице, то значение всего выражения F должно быть равно 1.

Тех данных, которые есть в таблице по каждой из 8 переменных выражения F, нам вполне достаточно для решения.

Проверим выражение номер 1:

? /\ 1 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 0 )
по второй строчке таблицы x1=1, х4=0 мы с вами видим что F возможно и может быть равным = 1, если все остальные переменные равны 1 (1 /\ ? /\ ? /\ 1 /\ ? /\ ? /\ ? /\ ? )
по третьей строчке таблицы x4=1, х8=1 мы с вами видим что F=0 (? /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ 0 ), а в таблице у нас F=1, и это значит, что выражение под номером один нам ТОЧНО НЕ ПОДХОДИТ .

Проверим выражение номер 2:

по первой строчке таблицы x2=0, х8=1 мы с вами видим что F возможно и может быть равным = 0, если все остальные переменные равны 0 (? V 0 V ? V ? V ? V ? V ? V 0 )
по второй строчке таблицы x1=1, х4=0 мы с вами видим что F = 1 (1 V ? V ? V 1 V ? V ? V ? V ? )
по третьей строчке таблицы x4=1, х8=1 мы с вами видим что F возможно и может быть равным = 1, если хотя бы одна из оставшихся переменных будет равна 1 (? V ? V ? V 0 V ? V ? V ? V 0 )

Проверим выражение номер 3:

по первой строчке таблицы x2=0, х8=1 мы с вами видим что F=0 (? /\ 0 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 1 )
по второй строчке таблицы x1=1, х4=0 мы с вами видим что F =0 (0 /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ ? ), а в таблице у нас F=1, и это значит, что выражение под номером три нам ТОЧНО НЕ ПОДХОДИТ .

Проверим выражение номер 4:

по первой строчке таблицы x2=0, х8=1 мы с вами видим что F=1 (? V 1 V ? V ? V ? V ? V ? V 0 ), а в таблице у нас F=0, и это значит, что выражение под номером четыре нам ТОЧНО НЕ ПОДХОДИТ .

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

Таблица истинности - это таблица, которая описывает логическую функцию. Логическая функция здесь - это функция, у которой значения переменных и значение самой функции выражают истинность. Например, они принимают значения «истина» либо «ложь» (true либо false, 1 либо 0).

Таблицы истинности применяются для определения значения какого-либо высказывания для всех возможных случаев значений истинности высказываний, которые его составляют. Количество всех существующих комбинаций в таблице находится по формуле N=2*n; где N - общее количество возможных комбинаций, n - число входных переменных. Таблицы истинности нередко используются в цифровой технике и булевой алгебре, чтобы описать работу логических схем.

Таблицы истинности для основных функций

Примеры : конъюнкция - 1&0=0, импликация - 1→0=0.

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

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

Последовательность построения (составления) таблицы истинности:

Определить количество N используемых переменных в логическом выражении.
Вычислить количество всевозможных наборов значений переменных M = 2 N , равное количеству строк в таблице.
Подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество логических операций.
Озаглавить столбцы таблицы названиями переменных и названиями логических операций.
Заполнить столбцы логических переменных наборами значений, например, от 0000 до 1111 с шагом 0001 в случае для четырех переменных.
Заполнить таблицу истинности по столбцам со значениями промежуточных операций слева направо.
Заполнить окончательный столбец значений для функции F.

Таким образом, можно составить (построить) таблицу истинности самостоятельно.

Составить таблицу истинности онлайн

Заполните поле ввода и нажмите OK. T - истина, F - ложь. Рекомендуем добавить страницу в закладки или сохранить в социальной сети.

Обозначения

Множества или выражения большими буквами латинского алфавита: A, B, C, D...
A" - штрих - дополнения множеств
&& - конъюнкция ("и")
|| - дизъюнкция ("или")
! - отрицание (например, !A)
\cap - пересечение множеств \cap
\cup - объединение множеств (сложение) \cup
A&!B - разность множеств A∖B=A-B
A=>B - импликация "Если..., то"
AB - эквивалентность

Продолжительность урока: 45 мин

Тип урока: комбинированный:

проверка знаний – устная работа;
новый материал – лекция;
закрепление – практические упражнения;
проверка знаний – задания для самостоятельной работы.

Цели урока:

дать понятие таблицы истинности;
закрепление материала предыдущего урока “Алгебра высказываний”;
использование информационных технологий;
привитие навыка самостоятельного поиска нового материала;
развитие любознательности, инициативы;
воспитание информационной культуры.

План урока:

Организационный момент (2 мин).
Повторение материала предыдущего урока (устный опрос) (4 мин).
Объяснение нового материала (12 мин).
Закрепление

разбор примера (5 мин);
практические упражнения (10 мин);
задания для самостоятельной работы (10 мин).

Обобщение урока, домашнее задание (2 мин).

Оборудование и программный материал:

белая доска;
мультимедийный проектор;
компьютеры;
редактор презентаций MS PowerPoint 2003;
раздаточный справочный материал “Таблицы истинности”;
демонстрация презентации “Таблицы истинности”.

Ход урока

I. Организационный момент

Мы продолжаем изучение темы “Основы логики”. На предыдущих уроках мы увидели, что логика достаточно крепко связана с нашей повседневной жизнью, а также увидели, что почти любое высказывание можно записать в виде формулы.

II. Повторение материала предыдущего урока

Давайте вспомним основные определения и понятия:

Вопрос	Ответ
1. Какое предложение является высказыванием?	Повествовательное предложение, в котором что-либо утверждается или отрицается
2. На какие виды делятся высказывания по своей структуре?	Простые и сложные
3. Истинность каких высказываний является договорной?	Простых
4. Истинность каких высказываний вычисляется?	Сложных
5. Как обозначаются простые высказывания в алгебре высказываний?	Логическими переменными
6. Как обозначается истинность таких высказываний?	1 и 0
7. Что связывает переменные в формулах алгебры высказываний?	Логические операции
8. Перечислите их.	Инверсия (отрицание) Конъюнкция (умножение) Дизъюнкция (сложение) Импликация (следование) Эквиваленция (равносильность)
9. Определите, соответствует ли формула сложному высказыванию. Назовите простые высказывания. Определите причину несоответствия. (Задание на экране)	Нет, неправильно поставлен знак
10. Определите, соответствует ли формула сложному высказыванию. Назовите простые высказывания. Определите причину несоответствия. (Задание на экране)	Да

III. Объяснение нового материала

Последние два примера относятся к сложным высказываниям. Как же определить истинность сложных высказываний?

Мы говорили, что она вычисляется. Для этого в логике существуют таблицы для вычисления истинности составных (сложных) высказываний. Они называются таблицами истинности.

Итак, тема урока ТАБЛИЦЫ ИСТИННОСТИ.

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

3.2) Разберем подробнее каждую логическую операцию в соответствии с ее определением:

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

Эта операция относится только к одной переменной, поэтому для нее отведено только две строки, т.к. одна переменная может иметь одно из двух значений: 0 или 1.

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

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

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

Можно убедиться, что таблица похожа на таблицу сложения кроме последнего действия. В двоичной системе счисления 1 + 1 = 10, в десятичной – 1 + 1 = 2. В логике значения переменной 2 невозможно, рассмотрим 10 с точки зрения логики: 1 – истинно, 0 – ложно, т.о. 10 – истинно и ложно одновременно, чего быть не может, поэтому последнее действие строго опирается на определение.

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

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

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

3.3) Разберем алгоритм составления таблицы истинности для сложного высказывания:

3.4) Рассмотрим пример составления таблицы истинности для сложного высказывания:

Пример. Построить таблицу истинности для формулы: А U В -> ¬А U С.

Решение (Рисунок 2)

Из примера видно, что таблицей истинности является не все решение, а только последнее действие (столбец, выделенный красным цветом).

IV. Закрепление.

Для закрепления материала вам предлагается решить самостоятельно примеры под буквами а, б, в, дополнительно г–ж (Рисунок 3).

V. Домашнее задание, обобщение материала.

Домашнее задание дано вам также на экране монитора (Рисунок 4)

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

Демонстрационный вариант ЕГЭ 2019 г. – задание № 2

Миша заполнял таблицу истинности функции (¬x /\ ¬y) \/ (y≡z) \/ ¬w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x,
y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Если бы функция была задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имел бы вид

то первому столбцу соответствовала бы переменная y, а второму столбцу – переменная x. В ответе следовало бы написать yx.

(¬x ¬y)+(y≡z)+¬w=0

w=1 w должно быть истинным; w — последний

y и z должны быть разными, поэтому перед последним, это x. первые два y и z или z и y.

y и x не могут быть ложными одновременно.первый — z.

Ответ: zyxw

Демонстрационный вариант ЕГЭ 2018 г. – задание № 2

Логическая функция F задаётся выражением ¬x \/ y \/ (¬z /\ w). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F ложна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z

В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т.д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Если бы функция была задана выражением ¬x\/y, зависящим от двух переменных: x и y, и был приведён фрагмент её таблицы истинности, содержащий все наборы аргументов, при которых функция истинна.

Тогда первому столбцу соответствовала бы переменная y, а второму столбцу – переменная x. В ответе следовало бы написать: yx.

Ответ: xzwy

Логическая функция F задаётся выражением x /\ ¬y /\ (¬z \/ w ).

На рисунке приведён фрагмент таблицы истинности функции F , содержащий все наборы аргументов, при которых функция F истинна.

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

В ответе напишите буквы w , x , y , z в том порядке, в котором идут

соответствующие им столбцы (сначала – буква, соответствующая первому

столбцу; затем – буква, соответствующая второму столбцу, и т.д.) Буквы

в ответе пишите подряд, никаких разделителей между буквами ставить

не нужно.

Демонстрационный вариант ЕГЭ 2017 г. – задание№2

Решение:

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

Переменной ¬y должен соответствовать тот столбец, в котором все значения равны 0 .

Дизъюнкция (логическое сложение) двух высказываний истинна тогда и только тогда, когда истинно хотя бы одно высказывание.
Дизъюнкция ¬z \/ y z=0 , w=1 .

Таким образом, переменной ¬z w соответствует столбец с переменной 4 (4 столбец).

Ответ: zyxw

Демонстрационный вариант ЕГЭ 2016 г. – задание№2

Логическая функция F задаётся выражением (¬z)/\x \/ x/\y. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z .

В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая 1-му столбцу; затем – буква, соответствующая 2-му столбцу; затем – буква, соответствующая 3-му столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример . Пусть задано выражение x → y, зависящее от двух переменных x и y, и таблица истинности:

Тогда 1-му столбцу соответствует переменная y, а 2-му столбцу
соответствует переменная x. В ответе нужно написать: yx.

Решение:

1. Запишем заданное выражение в более простых обозначениях:

¬z*x + x*y = x*(¬z + y)

2. Конъюнкция (логическое умножение) истинна тогда и только тогда, когда истинны все высказывания. Следовательно, чтобы функция (F ) была равна единице (1 ), нужно, чтобы каждый множитель был равен единице (1 ). Таким образом, при F = 1 , переменной х должен соответствовать тот столбец, в котором все значения равны 1 .

3. Рассмотрим (¬z + y) , при F = 1 данное выражение также равно 1(см. пункт 2).

4. Дизъюнкция (логическое сложение) двух высказываний истинна тогда и только тогда, когда истинно хотя бы одно высказывание.
Дизъюнкция ¬z \/ y в данной строке будет истинна только если

z = 0; y = 0 или y = 1;
z = 1; y = 1

5. Таким образом, переменной ¬z соответствует столбец с переменной 1 (1 столбец), переменной y

Ответ: zyx

КИМ ЕГЭ 2016 (досрочный период) – задание№2

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

(x /\ y /\¬z) \/ (x /\ y /\ z) \/ (x /\¬y /\¬z).

На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т.д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Решение:

Запишем заданное выражение в более простых обозначениях:

(x*y*¬z) + (x*y*z) + (x*¬y*¬z)=1

Это выражение истинно тогда, когда хотя бы один из (x*y*¬z) , (x*y*z) , (x*¬y*¬z) равняется 1. Конъюнкция (логическое умножение) истинна тогда и только тогда, когда истинны все высказывания.

Хотя бы одна из этих дизъюнкции x*y*¬z; x*y*z; x*¬y*¬z будет истинна только если х=1 .

Таким образом, переменной х соответствует столбец с переменной 2 (2 столбец).

Пусть y- перем.1, z- прем.3. Тогда, в первом случае x*¬y*¬z будет истинна, во втором случае x*y*¬z , а в третьем x*y*z.

Ответ: yxz

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует F?

X	Y	Z	F
0	0	0	0
1	0	1	1
0	1	0	1

1) X ∧ Y ∧ Z 2) ¬X ∨ Y ∨¬Z 3) X ∧ Y ∨ Z 4) X ∨ Y ∧ ¬Z

Решение:

1) X ∧ Y ∧ Z = 1.0.1 = 0 (не соответствует на 2-й строке)

2) ¬X ∨ Y ∨¬Z = ¬0 ∨ 0 ∨ ¬0 = 1+0+1 = 1 (не соответствует на 1-й строке)

3) X ∧ Y ∨ Z = 0.1+0 = 0 (не соответствует на 3-й строке)

4) X ∨ Y ∧ ¬Z (соответствует F)

X ∨ Y ∧ ¬Z = 0 ∨ 0 ∧ ¬0 = 0+0.1 = 0

X ∨ Y ∧ ¬Z = 1 ∨ 0 ∧ ¬1 = 1+0.0 = 1

X ∨ Y ∧ ¬Z = 0 ∨ 1 ∧ ¬0 = 0+1.1 = 1

Ответ: 4

Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F?

A	B	C	F
0	1	1	1
1	0	0	0
1	0	1	1

1) (A → ¬B) ∨ C 2) (¬A ∨ B) ∧ C 3) (A ∧ B) → C 4) (A ∨ B) → C

Решение:

1) (A → ¬B) ∨ C = (1 → ¬0) ∨ 0 = (1 → 1) + 0 = 1 + 0 = 1 (не соответствует на 2-й строке)

2) (¬A ∨ B) ∧ C = (¬1 ∨ 0) ∧ 1 = (0+0).1 = 0 (не соответствует на 3-й строке)

3) (A ∧ B) → C = (1 ∧ 0) → 0 = 0 → 0 = 1 (не соответствует на 2-й строке)

4) (A ∨ B) → C (соответствует F )

(A ∨ B) → C = (0 ∨ 1) → 1 = 1

(A ∨ B) → C = (1 ∨ 0) → 0 = 0

(A ∨ B) → C = (1 ∨ 0) → 1 = 1

Ответ: 4

Дано логическое выражение, зависящее от 6 логических переменных:

X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6

Сколько существует различных наборов значений переменных, при которых выражение истинно?

1) 1 2) 2 3) 63 4) 64

Решение:

Ложное выражение только в 1 случае: X1=0, X2=1, X3=0, X4=1, X5=0, X6=0

X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6 = 0 ∨ ¬1 ∨ 0 ∨ ¬1 ∨ 0 ∨ 0 = 0

Всего вариантов 2 6 =64, значит истинных

Ответ: 63

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

x1	x2	x3	x4	x5	x6	x7	F
0	1	0	1	1	1	0	0
1	1	0	1	0	1	0	1
0	1	0	1	1	0	1	0

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

1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7
4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7

Решение:

1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 = 0 + 1 + … = 1 (не соответствует на 1-й строке)

2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7 = 0 + 0 + 0 + 0 + 0 + 1 + 0 = 1 (не соответствует на 1-й строке)

3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7 = 1.0. …= 0 (не соответствует на 2-й строке)

4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 (соответствует F)

x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 = 1.1.1.1.1.1.1 = 1

x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 = 0. … = 0

Ответ: 4

x1	x2	x3	x4	x5	x6	x7	x8	F
		0				1		1
1		0			1			0
			1				0	1

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

1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8

Решение:

1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8 = x1 . ¬x2 . 0 . … = 0 (не соответствует на 1-й строке)

2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8 (соответствует F)

3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 = … ¬x7 ∧ ¬x8 = … ¬1 ∧ ¬x8 = … 0 ∧ ¬x8 = 0 (не соответствует на 1-й строке)

4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8 = ¬x1 ∨ ¬x2 ∨ ¬x3 … = ¬1 ∨ ¬x2 ∨ ¬0 .. = 1 (не соответствует на 2-й строке)

Ответ: 2

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

x1	x2	x3	x4	x5	x6	x7	F
0	0	1	1	0	0	1	0
0	1	0	0	1	1	0	1
0	0	0	0	1	1	1	1
1	0	1	0	1	1	0	1
0	1	1	1	0	1	0	1

Укажите минимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение x5 совпадает с F.

Решение:

Минимально возможное число различных строк, в которых значение x5 совпадает с F = 4

Ответ: 4

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

x1	x2	x3	x4	x5	x6	x7	x8	F
0	0	1	1	0	0	1	0	0
0	1	0	0	1	1	0	1	1
0	0	0	0	1	1	1	1	1
1	0	1	0	1	1	0	1	1
0	1	1	1	0	1	0	0	1

Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение x6 не совпадает с F.

Решение:

Максимально возможное число = 2 8 = 256

Максимально возможное число различных строк, в которых значение x6 не совпадает с F = 256 — 5 = 251

Ответ: 251

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

x1	x2	x3	x4	x5	x6	x7	F
0	0	1	1	0	0	1	0
0	1	0	0	1	1	0	1
0	0	0	0	1	1	1	1
1	0	1	0	1	1	0	1
0	1	1	1	0	1	0	1

Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение ¬x5 ∨ x1 совпадает с F.

Решение:

1+0=1 — не совпадает с F

0+0=0 — не совпадает с F

0+1=1 — совпадает с F

1+0=1 — совпадает с F

2 7 = 128 — 3 = 125

Ответ: 125

Каждое логическое выражение A и B зависит от одного и того же набора из 6 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы. Каково минимально возможное число единиц в столбце значений таблицы истинности выражения A ∨ B?

Решение:

Ответ: 4

Каждое логическое выражение A и B зависит от одного и того же набора из 7 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы. Каково максимально возможное число единиц в столбце значений таблицы истинности выражения A ∨ B?

Решение:

Ответ: 8

Каждое логическое выражение A и B зависит от одного и того же набора из 8 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 5 единиц. Каково минимально возможное число нулей в столбце значений таблицы истинности выражения A ∧ B?

Решение:

2 8 = 256 — 5 = 251

Ответ: 251

Каждое логическое выражение A и B зависит от одного и того же набора из 8 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 6 единиц. Каково максимально возможное число нулей в столбце значений таблицы истинности выражения A ∧ B?

Решение:

Ответ: 256

Каждое из логических выражений A и B зависит от одного и того же набора из 5 переменных. В таблицах истинности обоих выражений нет ни одной совпадающей строки. Сколько единиц будет содержаться в столбце значений таблицы истинности выражения A ∧ B?

Решение:

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

Ответ: 0

Каждое из логических выражений A и B зависит от одного и того же набора из 6 переменных. В таблицах истинности обоих выражений нет ни одной совпадающей строки. Сколько единиц будет содержаться в столбце значений таблицы истинности выражения A ∨ B?

Решение:

(a . ¬c) + (¬b . ¬c)

Когда с равно 1, F равна нулю так что последний столбец c.

Xтобы определить первый и второй столбцы, мы можем использовать значения из 3-го ряда.

(a . 1) + (¬b . 1) = 0

Ответ: abc

Логическая функция F задаётся выражением (a ∧ c)∨ (¬a ∧ (b ∨ ¬c)). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.

¬a. b

?	?	?	F
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	1	0
1	1	1

Исходя из того, что при a=0 и c=0, то F=0, и данных из второй строки, мы можем сделать вывод, что в третьем стоблце располагается b .

Ответ: cab

Логическая функция F задаётся выражением x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.