Что выполняется первым конъюнкция или дизъюнкция

Таблицы истинности

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Инверсия
2. Конъюнкция
3. Дизъюнкция
4. Импликация
5. Эквиваленция
6. Штрих Шеффера
7. Стрелка Пирса

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

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

Примеры решения задач

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

I –

II –

III –

IV –

V –

VI –

Высказывания. Операции над высказываниями

Высказывание — утверждение, относительно которого можно сказать истинно (1, истина, true) оно или ложно (0, ложь, false).

Высказывания обозначаются заглавными латинскими буквами %%A, B, C, . %% или буквами с индексами %%A_1, B^2, C’, . %%.

Примеры

Следующие предложения являются высказываниями:

%%A_1%%: «Лондон — столица Австрии».
%%A_2%%: «Число 8 больше числа 3».
%%A_3%%: «Число 8 больше числа 13».
%%A_4%%: «Луна — спутник планеты Земля».

Причем высказывания %%A_1, A_3%% — ложные, а %%A_2, A_4%% — истинные.

Следующие предложения не являются высказываниями:

%%B_1%%: «Какой сегодня день недели?».
%%B_2%%: «%%2 + 3%%».
%%B_3%%: «Число %%x%% больше 3».

Мы не можем сказать о любом из высказываний %%B_1, B_2, B_3%% истинно оно или ложно. Например, в предложении %%B_3%% буква %%x%% — переменная. Если поставить какое либо значение вместо нее, например 8, то получим истинное высказывание.

Операции над высказываниями

Сложные высказывания построены из более простых, используя следующие логические знаки $$ \land, \lor, \rightarrow, \leftrightarrow, \overline<>, $$ которые имеют соответствующие названия: конъюнкция (логическое И), дизъюнкция (логическое ИЛИ), импликация (логические следование), эквиваленция (логическое равенство) и отрицание (логическое НЕ).

Пусть %%A%% и %%B%% — некоторые высказывания.

Конъюнкция

Конъюнкцией высказываний %%A%% и %%B%%

называется новое высказывание, обозначаемое %%A \land B%%, которое является истинным тогда и только тогда, когда высказывания %%A%% и %%B%% истины. Читается как %%A%% и %%B%%.

Рассмотрим конъюнкцию высказывний %%A_1%% и %%A_2%%, которая записывается как %%A_1 \land A_2%% и читается как «Генуя — столица Австрии и число 8 больше числа 3». Это высказывание ложно, так как высказывание %%A_1%% ложно. Другими словами, конъюнкция является ложной тогда и только тогда, когда хотя бы одно из высказываний ложно.

Рассмотрим произвольные высказывания %%A%% и %%B%% и полученное из них высказывание %%A \land B%%. Высказывания %%A, B%% могут быть как ложными, так и истинными. Возможны следующие варианты:

1. %%A%% ложно, %%B%% ложно;
2. %%A%% ложно, %%B%% истинно;
3. %%A%% истинно, %%B%% ложно;
4. %%A%% истинно, %%B%% истинно;

В каждом их этих случаев, вычислив значение конъюнкции высказываний %%A \land B%%, получим следующую таблицу, которая называется таблицей истинности.

%%A%%	%%B%%	%%A \land B%%
%%0%%	%%0%%	%%0%%
%%0%%	%%1%%	%%0%%
%%1%%	%%0%%	%%0%%
%%1%%	%%1%%	%%1%%

Где %%1%% обозначает истинное высказывание, %%0%% — ложное высказывание.

Операцию конъюникции можно распространить и на несколько высказываний. Пусть %%A_1, A_2, . A_n%% — высказывания. Тогда высказывание %%A_1 \land A_2 \land . \land A_n%%, являющееся конъюнкцией высказываний %%A_1, A_2, . A_n%%, будет истинным тогда и только тогда, когда все высказывания будут истинными.

Дизъюнкция

Дизъюнкцией высказываний %%A%% и %%B%%

называется новое высказывание, обозначаемое %%A \lor B%%, которое является ложным тогда и только тогда, когда высказывания %%A%% и %%B%% ложны. Читается как %%A%% или %%B%%.

Рассмотрим дизъюнкцию высказывний %%A_1%% и %%A_2%%, которая записывается как %%A_1 \lor A_2%% и читается как «Москва — столица Австрии или число 8 больше числа 3». Это высказывание истинно, так как высказывание %%A_2%% истинно. Другими словами, дизъюнкция является истинной тогда и только тогда, когда хотя бы одно из высказываний истино.

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

%%A%%	%%B%%	%%A \lor B%%
%%0%%	%%0%%	%%0%%
%%0%%	%%1%%	%%1%%
%%1%%	%%0%%	%%1%%
%%1%%	%%1%%	%%1%%

Аналогично конъюнкции, операцию дизъюнкции можно распространить и на несколько высказываний. Пусть %%A_1, A_2, . A_n%% — высказывания. Тогда высказывание %%A_1 \lor A_2 \lor . \lor A_n%%, являющееся дизъюнкцией высказываний %%A_1, A_2, . A_n%%, будет ложным тогда и только тогда, когда все высказывания будут ложными.

Импликация

Импликацией высказываний %%A%% и %%B%% называется

новое высказывание, обозначаемое %%A \rightarrow B%%, которое является ложным тогда и только тогда, когда высказывание %%A%% истинно, %%B%% ложно. Читается как: «Если %%A%%, то %%B%%»; «%%A%% влечет %%B%%»; «из %%A%% следует %%B%%»; «%%A%% достаточно для %%B%%»; %%B%% необходимо для %%A%%».

Рассмотрим импликацию высказывний %%A_2%% и %%A_1%%, которая записывается как %%A_2 \rightarrow A_1%% и читается как «Если число %%8%% больше числа %%3%%, то Москва — столица Австрии». Это высказывание ложно, так как высказывание %%A_2%% истинно, а %%A_1%% ложно.

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

%%A%%	%%B%%	%%A \rightarrow B%%
%%0%%	%%0%%	%%1%%
%%0%%	%%1%%	%%1%%
%%1%%	%%0%%	%%0%%
%%1%%	%%1%%	%%1%%

Эквиваленция

Эквиваленцией высказываний %%A%% и %%B%%

называется новое высказывание, обозначаемое %%A \leftrightarrow B%%, которое является истинным тогда и только тогда, когда высказывание %%A%% и %%B%% одновременно истинны или ложны. Читается как: «%%A%% равносильно %%B%%»; «%%A%% необходимо и достаточно для %%B%%»; «%%A%% тогда и только тогда, когда %%B%%».

Рассмотрим импликацию высказывний %%A_1%% и %%A_2%%, которая записывается как %%A_1 \leftrightarrow A_2%% и читается как «Москва — столица Австрии тогда и только тогда, когда число %%8%% больше числа %%3%%». Это высказывание ложно, так как высказывание %%A_2%% истинно, а %%A_1%% ложно.

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

%%A%%	%%B%%	%%A \leftrightarrow B%%
%%0%%	%%0%%	%%1%%
%%0%%	%%1%%	%%0%%
%%1%%	%%0%%	%%0%%
%%1%%	%%1%%	%%1%%

Также эквиваленцию можно выразить через импликацию и конъюнкцию, тогда

$$ A \leftrightarrow B = (A \rightarrow B) \land (B \rightarrow A) $$

Покажем это, используя таблицы истинности.

%%A%%	%%B%%	%%A \leftrightarrow B%%	%%A \rightarrow B%%	%%B \rightarrow A%%	%%(A \rightarrow B) \land (B \rightarrow A)%%
%%0%%	%%0%%	%%1%%	%%1%%	%%1%%	%%1%%
%%0%%	%%1%%	%%0%%	%%1%%	%%0%%	%%0%%
%%1%%	%%0%%	%%0%%	%%0%%	%%1%%	%%0%%
%%1%%	%%1%%	%%1%%	%%1%%	%%1%%	%%1%%

Как видно из таблицы истинности столбцы %%A \leftrightarrow B%% и %%(A \rightarrow B) \land (B \rightarrow A)%% имеют одни и те же значения при одинаковых наборах значений %%A%% и %%B%%, что говорит о равенстве этих двух формул.

Отрицание

Отрицанием высказывания %%A%%

Рассмотрим отрицание высказывния %%A_1%%, которое записывается как %%\overline%% и читается как «неверно, что Москва — столица Австрии». Это высказывание истинно, так как высказывание %%A_1%% ложно.

Разбор 2 задания ЕГЭ по информатике

2-е задание: «Таблицы истинности»
Уровень сложности — базовый,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 3 минуты.

Проверяемые элементы содержания: Умение строить таблицы истинности и логические схемы

«Игнорирование прямо указанного в условии задания требования, что заполненная таблица истинности не должна содержать одинаковых строк. Это приводит к внешне правдоподобному, но на самом деле неверному решению»

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

операция	пояснение	в программировании
¬ A, A	не A (отрицание, инверсия)	not(A)
A ∧ B, A ⋅ B	A и B (логическое умножение, конъюнкция)	A and B
A ∨ B, A + B	A или B (логическое сложение, дизъюнкция)	A or B
A → B	импликация (следование)	A
A ↔ B, A ≡ B, A ∼ B	эквиваленция (эквивалентность, равносильность)	A==B (python) A=B(pascal)
A ⊕ B	строгая дизъюнкция	A != B (python)

Таблица истинности операции НЕ

Таблица истинности операции И (конъюнкция)

Таблица истинности операции ИЛИ (дизъюнкция)

Таблица истинности операции Импликация (если…, то…)

Таблица истинности операции Эквивалентность (тогда и только тогда, …)

A	B	A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

• если нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», импликация, равносильность

• логическое произведение X∙Y∙Z∙… равно 1, т.е. выражение является истинным, только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)
• логическая сумма X+Y+Z+… равна 0, т.е. выражение является ложным только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)

О преобразованиях логических операций читайте здесь.

Решение заданий 2 ЕГЭ по информатике

Плейлист видеоразборов задания на YouTube:

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

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

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

Перем.1	Перем.2	Перем.3	Перем.4	F
.	.	.	.	F
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	1	0	0	0

В ответе запишите буквы в том порядке, в котором идут соответствующие им столбцы.

✍ Решение:

Отобразим перебор всех значений использующихся в выражении переменных (всю таблицу истинности). Поскольку в выражении используются 4 переменных, то строк таблицы будет 2 4 =16:

✎ Способ 2. Программирование:
Язык python:

print(‘x y z w’) for x in 0, 1: for y in 0, 1: for z in 0, 1: for w in 0, 1: F = (not(x) or y or z) and (x or not(z) or not(w)) if not(F): print(x, y, z, w)

Язык pascalAbc.net:

begin writeln(‘x’:7, ‘y’:7, ‘z’:7,’w’:7); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not((not x or y or z) and (x or not z or not w)) then writeln(x:7, y:7, z:7,w:7); end.

Ответ:

✎ Способ 3. Логические размышления:

• Внешняя операция выражения — конъюнкция (∧). Во всех указанных строках таблицы истинности функция принимает значение 0 (ложь). Конъюнкция ложна аж в трех случаях, поэтому проверить на ложь очень затруднительно. Тогда как конъюнкция истинна (= 1) только в одном случае: когда все операнды истинны. Т.е. в нашем случае:
• Общая идея дальнейшего решения такова: поскольку внешняя операция — конъюнкция, и результат ее истинен, когда оба сомножителя в скобках будут истинны (=1), то нам необходимо сначала составить все наборы таблицы истинности для обоих сомножителей в скобках. Затем, так как конъюнкция подразумевает пересечение, необходимо сопоставить обе таблицы истинности и выбрать для каждого подходящего набора первого сомножителя подходящий (подходящие) набор (наборы) второго сомножителя. НО! так как у нас в задании известны только наборы для F = 0, то мы сопоставлять будем наборы, которые возвращают ложь. Теперь подробно.
• Разобьём исходное выражение на две части и составим таблицу истинности отдельно для двух частей.
• Для сомножителя (¬x ∨ y ∨ z):
  

  x	y	z	результат
  0	0	0	1
  0	0	1	1
  0	1	0	1
  0	1	1	1
  1	0	0	0
  1	0	1	1
  1	1	0	1
  1	1	1	1

• Получили ложь в одном наборе, так как дизъюнкция (∨) ложна только тогда, когда ложны все операнды.
• Для сомножителя (x ∨ ¬z ∨ ¬w):
  

  x	z	w	результат
  0	0	0	1
  0	0	1	1
  0	1	0	1
  0	1	1	0
  1	0	0	1
  1	0	1	1
  1	1	0	1
  1	1	1	1

• Соответственно, опять получили ложь в одном наборе, когда ложны все операнды.
• Учтем, что нам нужно выбрать и «пересечь» (так как внешняя операция ∧) из всех наборов только те, которые возвращают ложь (так как по заданию известны только строки, где F = 0):

Результат: xwzy

🎦 Видео решения 169 задания К.Полякова (бескомпьютерный вариант):

📹 Видеорешение на RuTube здесь

Миша заполнял таблицу истинности функции:

но успел заполнить лишь фрагмент из трех различных ее строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z:

Перем.1	Перем.2	Перем.3	Перем.4	F
.	.	.	.	F
1	1	0
1	0	0
1	1	0	0

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

В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы.

• Решим задание методом построения полной таблицы истинности.
• Посчитаем общее количество строк в таблице истинности и построим ее:

Результат: ywxz

✎ Способ 2. Программирование:

begin writeln(‘x’:7, ‘y’:7, ‘z’:7,’w’:7); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not((not z and (x xor y)) <= not(y or w)) then writeln(x:7, y:7, z:7,w:7); end.

Сопоставив их с исходной таблицей, получим результат: ywxz

print (‘x y z w’) for x in 0,1: for y in 0,1: for z in 0,1: for w in 0,1: F=(not z and not(x==y))<=(not(y or w)) if not F: print (x,y,z,w)

Результат: ywxz

🎦 Доступно видео решения этого задания (бескомпьютерный вариант):

📹 Видеорешение на RuTube здесь

🎦 Видео (решение 2 ЕГЭ в Excel):

📹 Видеорешение на RuTube здесь
📹 Видеорешение на RuTube здесь (Программирование)

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

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

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

Перем.1	Перем.2	Перем.3	Перем.4	F
.	.	.	.	F
0	1	0	0	1
1	1	0	0	1
1	1	0	1	1

В ответе запишите буквы в том порядке, в котором идут соответствующие им столбцы.

✍ Решение:

Результат: cbad

🎦 (Бескомьютерный вариант) Предлагаем подробный разбор посмотреть на видео:

📹 Видеорешение на RuTube здесь

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

Перем. 1	Перем. 2	Перем. 3	Перем. 4	F
.	.	.	.	F
1	0	0	0	0
1	1	0	0	0
1	1	1	0	0

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

✍ Решение:

✎ Логические размышления (бескомпьютерный вариант):

Результат: xzwy

✎ Способ 2. Программирование:
Язык pascalABC.NET:

begin writeln(‘x ‘,’y ‘,’z ‘,’w ‘); for var x:=false to true do for var y:=false to true do for var z:=false to true do for var w:=false to true do if not(not x or y or(not z and w)) then writeln(x:7,y:7,z:7,w:7); end.

🎦 (бескомпьютерный вариант) Подробное решение данного 2 задания из демоверсии ЕГЭ 2018 года смотрите на видео:

📹 Видеорешение на RuTube здесь

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

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

Перем.1	Перем.2	Перем.3	Перем.4	F
.	.	.	.	F
0	0	0
0	1	0	1	0
1	0	0

Результат: xwzy

🎦 Видеорешение (бескомпьютерный вариант):

📹 Видеорешение на RuTube здесь

Задания для тренировки

Каждое из логических выражений F и G содержит 5 переменных. В табл. истинности для F и G есть ровно 5 одинаковых строк, причем ровно в 4 из них в столбце значений стоит 1.

Сколько строк таблицы истинности для F ∨ G содержит 1 в столбце значений?

✍ Решение:

• Поскольку в каждом из выражений присутствует 5 переменных, то эти 5 переменных порождают таблицу истинности из 32 строк: т.к. каждая из переменных может принимать оно из двух значений (0 или 1), то различных вариантов с пятью переменными будет 2 5 =32, т.е. 32 строки.
• Из этих 32 строк и для F и для G мы знаем наверняка только о 5 строках: 4 из них истинны (=1), а одна ложна (=0).
• Вопрос стоит о количестве строк = 1 для таб. истинности F ∨ G. Данная операция — дизъюнкция, которая ложна только в одном случае — если F = 0 и одновременно G = 0
• В исходных таблицах для F и G мы знаем о существовании только одного 0, т.е. в остальных строках может быть 1. Т.о., и для F и для G в 31 строке могут быть единицы (32-1=31), а лишь в одной — ноль.
• Тогда для F ∨ G только в одном случае будет 0, когда и F = 0 и G = 0:
  

  №	F	G	F ∨ G
  1	0	0	0
  2	0	1	1
  …	…	…	1
  32	…	…	1

• Соответственно, истинными будут все остальные строки:

Результат: 31

Подробное объяснение данного задания смотрите на видео:

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

Каково максимально возможное число единиц в столбце значений таблицы истинности выражения A ∨ B?

✍ Решение:

• Полная таблица истинности для каждого из выражений A и B состоит из 2 7 = 128 строк.
• В четырех из них результат равен единице, значит в остальных — 0.
• A ∨ B истинно в том случае, когда либо A = 1 либо B = 1, или и A и B = 1.
• Поскольку А = 1 только в 4 случаях, то чтобы получить максимальное количество единиц в результирующей таблице истинности (для A ∨ B), расположим все единицы т.и. для выражения A так, чтобы они были в строках, где B = 0, и наоборот, все строки, где B = 1, поставим в строки, где A = 0:
  

  A	B
  1	0
  1	0
  1	0
  1	0
  0	1
  0	1
  0	1
  0	1
  0	0
  …	…

• Итого получаем 8 строк.
• Если бы в задании требовалось найти минимальное количество единиц, то мы бы совместили строки со значением = 1, и получили бы значение 4.

Результат: 8

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

Каково максимально возможное число нулей в столбце значений таблицы истинности выражения A ∧ B?

✍ Решение:

• Полная таблица истинности для каждого из выражений A и B состоит из 2 8 = 256 строк.
• В шести из них результат равен единице, значит в остальных — 0.
• A ∧ B ложно в том случае, когда:
• Во всех случаях там где А=1 может стоять B=0, и тогда результат F = 0. Поскольку нам необходимо найти максимально возможное число нулей, то как раз для всех шести А=1 сопоставим B=0, и наоборот, для всех шести возможных B=1 сопоставим A=0
  

  A	B	F
  1	0	0
  1	0	0
  1	0	0
  1	0	0
  0	1	0
  0	1	0
  0	1	0
  0	1	0
  0	0	0
  …	…	…

• Поскольку строк всего 256, то вполне возможно, что все 256 из них возвратят в результате 0

Результат: 256

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

x1	x2	x3	x4	x5	x6	x7	F
1	0	0	1	1	1	1	0
0	1	0	0	1	0	1	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

✍ Решение:

• В первом внешняя операция (выполняется последней) — конъюнкция. Начнем рассмотрение с нее. Соответственно, проверяем по второй строке таб. ист-ти, там где F = 1, так как в таком случае все аргументы должны быть истинными (см. таб. истинности для конъюнкции).
• Если мы подставим в нее все аргументы выражения, то функция действительно возвращает истину. Т.е. пункт первый подходит:

Результат: 1

Решение 2 задания ГВЭ по информатике смотрите на видео:

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

(¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5) ∧ (x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5)

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

✍ Решение:

• Поскольку выражение включает 5 переменных, то таб. ист-ти состоит из 2 5 = 32 строк.
• Внешней операцией (последней) является конъюнкция (логическое умножение), а внутри скобок — дизъюнкция (логическое сложение).
• Обозначим первую скобку за А, а вторую скобку за B. Получим A ∧ B.
• Найдем сколько нулей существует для таб. истинности:

Теперь рассмотрим каждый случай отдельно:

¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5 = 0
и
x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 = 0.

Результат: 2

Подробное решение задания смотрите в видеоуроке:

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

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

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

✍ Решение:

• Полная таблица истинности будет иметь 2 6 = 64 строк (т.к. 6 переменных).
• 4 из них нам известны: в них x3 два раза не совпадает с F.
• Неизвестных строк:
• В неизвестных x3 может не совпадать с F, кроме того, в двух известных x3 не совпадает с F. Соответственно максимально возможное число строк с несовпадающими x3 и F, будет:

Результат: 62

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

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

Каким выражением может быть 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

✍ Решение:

• Рассмотрим отдельно каждый пункт и найдем последнюю операцию, которая должна быть выполнена (внешнюю).

2 пункт:

3 пункт:

Результат: 4

В видеоуроке рассмотрено подробное решение 2 задания:

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

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

№	Перем. 1	Перем. 2	Перем. 3	F
.	.	.	F
1	0	0	0	0
2	0	0	1	0
3	0	1	0	1
4	0	1	1	1
5	1	0	0	0
6	1	0	1	0
7	1	1	0	0
8	1	1	1	1

В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы.

✍ Решение:

• Сначала необходимо рассмотреть логическую операцию, которую мы будем выполнять в последнюю очередь — это логическое И (конъюнкция) или ∧. То есть внешнюю операцию:
• Конъюнкцию легче рассматривать по тем строкам таб. ист-ти, в которых F = 1, т.е. №3, №4, и №8
• Поскольку для конъюнкции функция истинна только тогда, когда все переменные истинны, то необходимо чтобы отдельно каждая скобка была истинна ((y → x) = 1 и (y → z)=1) и переменная z тоже была истинной (=1)
• Поскольку с выражениями в скобках сложней работать, определим сначала какому столбцу соответствует z. Для этого выберем строку (№3), где F = 1, а в остальных ячейках только одна единица, остальные — нули.
  

  №	Перем. 1	Перем. 2	Перем. 3	F
  3	0	1	0	1

• Таким образом, делаем вывод, что z находится во втором столбце (отсчет ведем слева):
  

  №	Перем. 1	Перем. 2	Перем. 3	F
  _	.	z	.	F

• Дальше нам необходимо рассмотреть две скобки, в которых находится операция импликации: (y → x) и (y → z). Обе эти скобки должны возвращать истину (=1). В таб. истинности для импликации, функция возвращает в результате 1 тогда, когда:
• вторая переменная (заключение) равна 1 (первая при этом может быть любой),
• вторая переменная (заключение) равна 0, а первая обязательно должна быть равна тоже 0.
• Рассмотрим скобку (y → x) и строку 4 таблицы:
  

  №	Перем. 1	z	Перем. 3	F
  4	0	1	1	1

• Для этой строки только y может быть равен 0, т.к. если x = 0, тогда y=1, и скобка в результате возвратит ложь (1 → 0 = 0). Соответственно, y находится в первом столбце. А x значит должен стоять в третьем:
  

  y

  z

  x

  F

Результат: yzx

Детальный разбор данного задания 2 ЕГЭ по информатике предлагаем посмотреть в видео: