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

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

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

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

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

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

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

A ¬ А
1 0
0 1

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

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

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

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

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

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

Источник

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

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

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

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

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

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

2 theory

1 7

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

1 11 5

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

1 8

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

1 11 6

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

1 9

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

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

2 egif 1

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

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

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

(¬x ∨ y ∨ z) ∧ (x ∨ ¬z ∨ ¬w)

Ниже приведен фрагмент таблицы истинности функции 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

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

✍ Решение:

izobrazhenie 2021 03 19 091423

izobrazhenie 2021 03 19 093335

izobrazhenie 2021 03 19 093937

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.

Ответ:

0

Результат: xwzy

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

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

(¬z ∧ ¬(x ≡ y)) → ¬(y ∨ w)

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

000 19

000 20

Результат: 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)) false = 0, True = 1

Сопоставив их с исходной таблицей, получим результат: 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)) F=0 :

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

Результат: ywxz

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


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

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

¬a ∧ b ∧ (c ∨ ¬d)

Ниже приведен фрагмент таблицы истинности функции 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

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

Логическая функция 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 года смотрите на видео:

Логическая функция 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

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

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

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

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

✍ Решение:

Результат: 31

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

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

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

✍ Решение:

Результат: 8

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

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

✍ Решение:

Результат: 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

✍ Решение:

1111

11111

1111 1

11111 1

Результат: 1

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

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

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

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

✍ Решение:

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

¬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.

✍ Решение:

Результат: 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

✍ Решение:

1 28

Результат: 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 в том порядке, в котором идут соответствующие им столбцы.

✍ Решение:

Результат: yzx

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

Источник

Импликация и логическое следование

Импликация

Ещё одна важная связка \(A\to B\), называется импликацией. Она ложна только для комбинации \(\T\to \F\), что интерпретируется как «из истины нельзя получить ложь». В остальных случаях она истинна:

im14

Из истины «следует» истина, поэтому \(\T \to \T\) это \(\T\). Из лжи можно вывести что угодно, поэтому \(\F \to \F\) и \(\F \to \T\) считаются истинными. Аргументы импликации называются посылкой и следствием.

Для высказываний интерпретация импликации, как логического следования выглядит странной.
Так \((2\cdot 2=4)

\) «Солнце это звезда» — истинная формула, хотя посылка и следствие между собой ни как не связаны.

Лучше ситуация для предикатов. Например, в арифметике при любом \(x\) истинно утверждение: «если \(x 2) \to (x

Логическое следование

Пусть \(P=P(A,B(x). )\) и \(Q=Q(A,C(x,y). )\) формулы, зависящие от высказываний и предикатов. Эти формулы равны \(\T\) или \(\F\) при определённых значениях, входящих в них элементарных утверждений.

im15

A. \] Так, первое следование означает, что если \(A\) истинно, то для любого \(B\), дизъюнкция \(A\vee B\) будет истинной. Справедлива теорема:

Например, формула \(A \to (A\vee B)\) — общезначима. Импликация \(P\to Q\) (бинарная функция), в отличие от следования \(P\Rightarrow Q\), определена и когда \(P\) ложно. При логическом же следовании подразумевается истинность посылки. В частности, справедливо правило modus ponens:

означающее, что если обе посылки \(P\) и \(P\to Q\) истинны, то истинна и формула \(Q\). Если \(P\equiv\F\), то \(Q\) — это \(\T\) или \(\F\). Стоит проверить общезначимость формулы \(P\,\&\,(P\to Q) \to Q\).

Следствие обладает транзитивностью: \[если

Следствие в общем случае не симметрично. Так, \(A

A\vee B\) ( справедливо только в одну сторону и из \(A\vee B\) не следует \(A\) (поэтому \(A\vee B \to A\) не тавтология. Тем не менее, существуют и следования в обе стороны: \(\Leftrightarrow\). Например: \(A\vee B

\Leftrightarrow B\vee A\) или двухстороннее правило: \[ A\,\&\, B

B. \] Вправо, это \(A\,\&\, B\Rightarrow A\), влево оно означает: когда обе посылки \(A\) и \(B\) истинны, истинна и их конъюнкция.

im17Двухсторонний вывод \(P\Leftrightarrow Q\) аналогичен функции эквивалентности \(P\equiv Q\). Утверждения: «если \(P\), то \(Q\) и наоборот», «\(P\) тогда и только тогда, когда \(Q\)» означают \(P\Leftrightarrow Q\).

Если \(P\Rightarrow X\Rightarrow Q\), то \(P\) называют достаточным условием, а \(Q\) — необходимым условием для \(X\). Когда необходимое и достаточное условия совпадают, то они совпадают и с \(X\): \(P\equiv Q\equiv X\).

Прямой логический вывод

S\vee Q. \] Действительно: так как \(P\) и \(\neg P\) не могут быть одновременно истинными, а посылки \(P \vee\, S\) и \(\neg P\vee Q \) истинны по определению, то истинно \(S\) или \(Q\). Если \(S\) — ложно, получается частный случай \((<\bf MP>)\). Стоит также проверить, что \((P\vee S) \,\&\,(\neg P \vee Q)

S\vee Q\) — это тавтология.

Вариантом резолюции является метод цепочек импликаций: \[ P\to S,

P\to Q. \] Если в каждой формуле выразить импликацию через дизъюнкцию (заменить \(P\to S\) на \(\neg P\vee S\)), то получится следование, совпадающее с резолюцией точностью до переобозначений: \[\neg P \vee \underline,

\neg \underline \vee Q

im18 Метод разбора случаев — ещё один пример прямых рассуждений. Пусть из \(P\) необходимо вывести \(Q\). Рассмотрим несколько утверждений, например, \(P_1\) и \(P_2\), объединение которых равно \(P\). Говорят, что \(P_1\) и \(P_2\) покрывают все возможные случаи. Если из каждого утверждения \(P_i\) следует \(Q\), то оно следует и из \(P=P_1\vee P_2\): \[ P_1\vee P_2,

Q. \] \(\lhd\) Докажем это правило при помощи резолюции: \[ \underline\vee P_2,

\neg \underline\vee Q,

Q. \] Формула и её отрицание подчёркнуты. В первом выводе это \(P_1\) и из формул \(P_1\vee P_2\) и \(\neg P_1\vee Q\) следует \(P_2\vee Q\). Во втором выводе формула и её отрицание — это \(P_2\), а резолюция приводит к \(Q\vee Q

Приведём в качестве неформального примера простую теорему:

\(\lhd\) Рассмотрим два случая: \(P_1: \mathrm(x)\,\&\,\mathrm(y)\) и \(P_2: \mathrm(x)\,\&\,\mathrm(y)\). По условию теоремы \(P_1\vee P_2\) является посылкой.
По определению \(\mathrm(x)\) и \(P_1\), существуют такие \(n,m\in \mathbb N\), что \(x=2n\) и \(y=2m\). Тогда \(x+y=2(n+m)\) — чётно (\(Q\)).
Во втором случае \(P_2:\) \(x=2n+1\), \(y=2m+1\) и \(x+y=2(n+m+1)\) также чётно (снова \(Q\)). Поэтому теорема истинна. \(\square\)

Доказательство от противного

im19

Доказательство от противного — исключительно важный обратный метод. В нём, вместо прямого заключения \(P

Q\), показывают, что \(P\) и отрицание \(Q\) противоречивы, т.е. из них следует всегда ложное утверждение, подобное \(A\,\&\,\neg A\equiv \F\):

Q. \] На рисунке область истинности формулы \(P\) является подмножеством области истинности \(Q\), поэтому отрицание \(Q\) (серый цвет) и \(P\) не пересекаются (\(P\,\&\,\neg Q\equiv \F\)). Несложно видеть, что \(\neg (P\, \&\, \neg Q)

P\to Q\). Дадим также формальное доказательство метода от противного.

\F\) истинно. Тогда по определению импликации \(P\,\&\,\neg Q\) ложно. Для \(\\) возможно 3 варианта \(\<\F,\,\F\>\), \(\<\F,\,\T\>\) и \(\<\T,\,\T\>\). Для всех них \(P\to Q\) истинно. Аналогично для логического следования в обратную сторону. \(\square\)

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

Косвенное доказательство — это частный случай метода от противного. В нём, вместо \(P \to Q\), выясняется, что \(\neg Q \to \neg P\). Если это так, то значит справедливо и \(P \to Q\): \[ \neg Q

Q. \] Фактически \(\neg Q\to \neg P\) равно \(Q\vee \neg P\), что эквивалентно \(P\to Q\).

Подобный метод вывода может показаться тривиальной тавтологией. Однако это не так. На практике берут отрицание \(\neg Q\). Из этой формулы логически выводят (иногда довольно сложным образом) формулу \(\neg P\). Если построен вывод \(\neg Q

\neg P\), то, как мы видели выше, формула \(\neg Q\to \neg P\) оказывается тавтологией. Именно на этом этапе, при помощи косвенного доказательства, выводится \(P\to Q\). Наконец, если посылка \(P\) считается истинной, то по правилу \((<\bf MP>)\) из \(P\) и \(P\to Q\) выводится \(Q\).

Классический пример рассуждения от противного, доказательство, что

\(\lhd\) В качестве \(P\) выступают стандартные аксиомы арифметики.
Необходимо доказать \(Q:

\sqrt<2>\neq n/m\), где \(n/m\) несократимая дробь.
Пусть \(\neg Q:

\sqrt<2>=n/m\). Тогда \(n^2=2m^2\) и следовательно \(n\) — чётно, т.е. \(n=2k\).
Но тогда \((2k)^2 = 2m^2\) или \(m^2 = 2k^2\), т.е. \(m\) — также чётно, а это противоречит несократимости дроби \(n/m\).
Поэтому \(Q\) истинно. \(\square\)

Источник

admin
Делаю сам
Adblock
detector