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

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

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

Примеры

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

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

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

Обозначения

Тема 1.7. Методы упрощения логических выражений. Методы решения логических задач.

Отрицание

Дизъюнкция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задание 1 #10050

\((x \wedge y) \vee (x \wedge \overline y) \vee (y\wedge z) \vee (z \wedge x)\)

Составьте её таблицу истинности. В качестве ответа введите количество наборов \((x,\) \(y,\) \(z),\) при которых функция равна 1.

1. Упростим \((x \wedge y) \vee (x \wedge \overline y).\)

По закону дистрибутивности \((y \wedge x) \vee (x \wedge \overline y)\) = \(x \wedge (y \vee \overline y).\) \(y \vee \overline y = 1\) (если \(y = 0,\) то \(\overline y \vee y = 1 \vee 0 = 1,\) если \(y = 1,\) то \(\overline y \vee y = 0 \vee 1 = 1).\) Тогда \(x \wedge (y \vee \overline y) = x \wedge 1 = x .\)

2. Упростим \((y\wedge z) \vee (z \wedge x).\) По закону дистрибутивности \((y\wedge z) \vee (z \wedge x) = z \wedge (y \vee x).\)

3. Получим: \((x \wedge y) \vee (x \wedge \overline y) \vee (y\wedge z) \vee (z \wedge x) = x \vee z \wedge (y \vee x).\)

4. В таблице истинности содержится 8 строчек (строк всегда \(2^n,\) где \(n\) - количество переменных). В нашем случае переменных 3.

5. Заполним таблицу истинности.

\[\begin{array}{|c|c|c|c|c|c|c|} \hline x & y & z & y \vee x & z \wedge (y \vee x) & F = x \vee z \wedge (y \vee x) \\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 1 & 0 & 1 & 0 & 0 \\ \hline 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 1 & 0 & 1 \\ \hline 1 & 0 & 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 0 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 & 1 & 1 & 1 \\ \hline \end{array}\]

Так как дизъюнкция \(x \vee z \wedge (y \vee x)\) истинна, если истинно хотя бы одно из входящих в нее высказываний, то для \(x = 1\) \(F = 1\) при любых \(y\) и \(z\) (строки 5-8 в таблице истинности).

Рассмотрим случай, когда \(x = 0.\) Тогда значение функции будет зависить от значения \(z \wedge (y \vee x).\) Если \(z \wedge (y \vee x)\) истинна, то и \(F\) истинна, если ложна, то \(F\) ложна. Рассмотрим случай, когда \(F = 1.\) Конъюнкция \((z \wedge (y \vee x))\) истинна, если все входящие в нее высказывания истинны, то есть \(y \vee x = 1\) и \(z = 1.\) \(x = 0,\) значит, \(y \vee x = 1,\) когда \(y = 1\) (строка 4).

Если же одно из высказываний, входящих в конъюнкцию, ложно, то вся конъюнкция ложна. Если \(x = 0\) и \(y = 0,\) то \(y \vee x = 0.\) Тогда \(z \wedge (x \vee y) = 0\) при любом \(z\) (строки 1-2). Так как \(x = 0,\) а второе высказывание, входящее в дизъюнкцию \((z \wedge (x \vee y)),\) тоже ложно, то и вся функция ложна. Если \(x = 0\) и \(y = 1,\) то \(y \vee x = 1.\) Если \(z = 0,\) \(z \wedge (y \vee x) = 0.\) Тогда \(F = 0\) (строка 3). Случай, когда \(z = 1,\) \(y = 1,\) \(x = 0,\) был рассмотрен в предыдущем абзаце.

Мы построили таблицу истинности. Видим, что в ней есть 5 наборов, при которых \(F = 1.\) Поэтому ответ: 5.

Ответ: 5

Задание 2 #10051

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

\((x \wedge \overline y \wedge z) \vee (x \rightarrow y)\)

Составьте её таблицу истинности. В качестве ответа введите количество наборов \((x,\) \(y,\) \(z),\) при которых функция равна 0.

\[\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline x & y & z & \overline y & x\wedge \overline y & x \wedge \overline y \wedge z & \overline x & \overline x \vee y & x \wedge \overline y \wedge z \vee \overline x \vee y \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ \hline 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1\\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\ \hline 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1\\ \hline 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\ \hline 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1\\ \hline \end{array}\]

1. \(x \rightarrow y\) = \(\overline x \vee y.\)

2. Заметим, что при \(y = 1\) \(F = 1,\) так как дизъюнкция истинна, если истинно хотя бы одно выражение, входящее в нее (строки 3-4, 7-8 в таблице истинности). Аналогично при \(\overline x = 1,\) то есть при \(x = 0,\) \(F = 1\) (строки 1-4).

3. При \(x = 1\) и \(y = 0\) \(\overline x \vee y = 0,\) \(x \wedge \overline y = 1.\) При \(z = 1\) \(x \wedge \overline y \wedge z = 1\) и \(F = 1,\) так как истинно одно из выражений (строка 6), а при \(z = 0\) \(x \wedge \overline y \wedge z = 0\) и \(F = 0,\) так как оба выражения, входящие в дизъюнкцию, ложны (строка 5).

По построенной таблице истинности видим, что для одного набора \((x,\) \(y,\) \(z)\) \(F = 0.\)

Ответ: 1

Задание 3 #10052

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

\((\overline{z \vee \overline y}) \vee (w \wedge (z \equiv y)) \)

Составьте её таблицу истинности. В качестве ответа введите сумму значений \(z,\) \(y\) и \(w,\) при которых \(F = 1.\)

\[\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline w & y & z & \overline y & z \vee \overline y & \overline{z \vee \overline y} & z \equiv y & w \wedge (z \equiv y) & \overline z \vee \overline y \vee w \wedge (z \equiv y) \\ \hline 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ \hline 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ \hline 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ \hline 1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ \hline \end{array}\]

1. \((\overline{z \vee \overline y}) = \overline z \wedge y \)

2. В таблице истинности будет \(2^3 = 8\) строк.

3. Если \(z = 1 \) и \(y = 1,\) \(то (z \equiv y) = 1 \) (так как эквивалентность истинна тогда и только тогда, когда оба высказывания одновременно ложны или истинны). \(\overline z \wedge y = 0\) \((0 \wedge 1 = 0).\) Если \(w = 1,\) \(w \wedge (z \equiv y) = 1\) \((1 \wedge 1 = 1)\) и \(F = 1,\) так как дизъюнкция истинна, если истинно хотя бы одно из входящих в нее высказываний (строка 8 в таблице истинности). Если \(w = 0,\) \(w \wedge (z \equiv y) = 0\) \((0 \wedge 1 = 0)\) и \(F = 0,\) так как оба высказывания, входящие в дизъюнкцию, ложны (строка 4).

4. Аналогично для \(z = 0, y = 0.\) \((z \equiv y) = 1,\) \(\overline z \wedge y = 0\) \((1 \wedge 0 = 0).\) Тогда снова значение функции будет зависеть от \(w.\) При \(w = 1\) \(w \wedge (z \equiv y) = 1,\) \(F = 1,\) так как одно из высказываний, входящих в дизъюнкцию, истинно (строка 5), а при \(w = 0\) \(w \wedge (z \equiv y) = 0,\) \(F = 0,\) так как все высказывания ложны (строка 1).

5. Если \(z = 0\) и \(y = 1,\) то \(\overline z \wedge y = 1\) \((1 \wedge 1 = 1).\) Так как \((z \equiv y) = 0\) (ведь значения \(z\) и \(y\) различны), будет ложна при любом \(w.\) Тогда, так как значение переменной \(w\) не будет влиять на значение функции, при \(z = 0\) и \(y = 1\) \(w\) может быть как 0, так и 1. \(F = 1,\) так как одно из высказываний, входящих в дизъюнкцию, истинно (строки 3, 7).

6. Если \(z = 1\) и \(y = 0,\) то \(\overline z \wedge y = 0 \wedge 0 = 0.\) Так как \((z \equiv y) = 0,\) \(w \wedge (z \equiv y) = w \wedge 0\) будет ложна при любом \(w\) (то есть \(w\) может быть и 0 и 1). Значит, при \(z = 1\) и \(y = 0\) \(F\) всегда будет ложна (так как оба высказывания, входящих в дизъюнкцию, ложны, строки 2, 5).

7. \(F = 1\) при следующих наборах \(z,\) \(y,\) \(w:\) (0, 0, 1), (0, 1, 1), (1, 1, 1), (0, 1, 0). Если просуммировать значения, то получим 7.

Ответ: 7

Задание 4 #10053

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

\(a \wedge ((\overline{b \wedge c}) \vee (a \wedge \overline b) \vee (\overline c \wedge a)) \)

Составьте её таблицу истинности. В качестве ответа введите сумму значений \(a,\) \(b\) и \(c,\) при которых \(F = 1.\)

\[\begin{array}{|c|c|c|c|} \hline a & b & c & F\\\hline 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 \\ \hline 0 & 1 & 0 & 0 \\ \hline 0 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 \\ \hline 1 & 0 & 1 & 1 \\ \hline 1 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 & 0 \\ \hline \end{array}\]

1. В таблице истинности \(2^3 = 8\) строк.

2. При \(a = 0\) \(F = 0\) при любых значениях \(b\) и \(c,\) так как конъюнкция истинна тогда и только тогда, когда все высказывания, входящие в нее, истинны (строки 1-4 в таблице истинности).

3. Рассмотрим случаи, когда \(a = 1.\) Если \(\overline {(b \wedge c)} \vee (a \wedge \overline b) \vee (\overline c \wedge a) = 1,\) то \(F = 1\) (так как оба высказывания будут истинны), иначе \(F = 0\) (так как одно высказывание будет ложно). По закону де Моргана \(\overline{b \wedge c} = \overline b \vee \overline c.\) Тогда, учитывая, что \(a = 1,\) \(\overline {(b \wedge c)} \vee (a \wedge \overline b) \vee (\overline c \wedge a) = \overline b \vee \overline c \vee \overline b \vee \overline c = \overline b \vee \overline c.\)

4. Если \(\overline b = 0\) и \(\overline c = 0\) (одновременно, то есть при \(b = 1\) и \(c = 1),\) то \(\overline b \vee \overline c = 0\) и \(F = 0\) (строка 8). В остальных случаях \(\overline b \vee \overline c = 1\) и \(F = 1\) (строки 5-7).

5. Наборы \((x,\) \(y,\) \(z),\) при которых \(F = 1:\) (1, 0, 0), (1, 1, 0), (1, 0, 1). Сумма значений равна 5.

Ответ: 5

Задание 5 #10054

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

\(((a \wedge b) \vee (b \wedge c)) \equiv ((d \rightarrow a) \vee (b \wedge \overline c)) \)

Составьте таблицу истинности. В качестве ответа введите сумму значений \(a,\) при которых \(F = 0.\)

\[\begin{array}{|c|c|c|c|c|} \hline a & b & c & d & F\\\hline 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 1 & 1 \\ \hline 0 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 & 1 \\ \hline 1 & 1 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 & 0 \\ \hline 1 & 1 & 0 & 1 & 1 \\ \hline 1 & 0 & 1 & 0 & 0 \\ \hline 1 & 0 & 0 & 1 & 0 \\ \hline 0 & 1 & 1 & 0 & 1 \\ \hline 1 & 0 & 1 & 1 & 0 \\ \hline 0 & 1 & 0 & 1 & 0 \\ \hline \end{array}\]

1. По закону дистрибутивности \((a \wedge b) \vee (b \wedge c) = b \wedge (a \vee c).\)

2. \(d \rightarrow a = \overline d \vee a.\)

3. \(((a \wedge b) \vee (b \wedge c)) \equiv ((d \rightarrow a) \vee (b \wedge \overline c)) = b \wedge (a \vee c) \equiv (\overline d \vee a \vee (b \wedge \overline c)) .\)

4. Если \(b = 0,\) то левая часть функции равна 0 \((0 \wedge (a \vee c) = 0).\) \(b \wedge \overline c = 0 \wedge \overline c = 0.\) Значит, для \(b = 0\) \(c\) может быть любым, так как не влияет на значение функции. \(F = 1,\) если \(\overline d \vee a = 0\) (тогда одно из выражений, входящих в дизъюнкцию, будет истинно). Это выполняется при \(\overline d = 0\) \((d = 1)\) и \(a = 0\) (строки 2, 3). При других \(d\) и \(a\) \(\overline d \vee a = 0,\) значит, \(F = 0,\) так как операция эквивалентности истинна тогда и только тогда, когда оба высказывания одновременно истинны или ложны (строки 1, 10 в таблице истинности).

5. Если \(b = 1,\) то \(b \wedge (a \vee c) = 1 \wedge (a \vee c) = a \vee c.\) \(b \wedge \overline c = 1 \wedge \overline c = \overline c.\) Тогда имеем, что \(a \vee c \equiv \overline d \vee a \vee \overline c.\) Если \(a = 1,\) то \(a \vee c = 1 \) и \(\overline d \vee a \vee \overline c = 1,\) так как дизъюнкция истинна, если хотя бы одно из выражений истинно (а в обеих дизъюнкциях есть \(a = 1).\) Тогда, если \(b = 1\) и \(a = 1,\) \(F = 1\) при любых \(c\) и \(d\) (строки 5, 7, 8, 11).

Если \(a = 0,\) то \(a \vee c = 0 \vee c = c,\) а \(\overline d \vee a \vee \overline c = \overline d \vee \overline c.\) Имеем: \(c \equiv (\overline d \vee \overline c).\) При \(c = 1\) \(1 \equiv \overline d.\) При \(d = 1\) \(F = 0,\) так как высказывания различны (строка 4), при \(d = 0\) \(F = 1,\) так как оба высказывания истинны (строка 14). При \(c = 0\) \(0 \equiv (\overline d \vee 1).\) Так как \(\overline d \vee 1\) - дизъюнкция, в которой одно из высказываний истинно, то и вся дизъюнкция истинна. Тогда \(0 \equiv 1,\) что неверно, значит, \(F = 0\) при любых \(d\) (строка 9, 16).

По построенной таблице видим, что \(F = 0\) при \(a = 0\) (строки 1, 4, 9, 10, 16) и при \(a = 1\) (строки 6, 12, 13, 15). Тогда сумма значений равна 0 * 5 + 1 * 4 = 4.

Ответ: 4

Задание 6 #10055

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

\((a \equiv (b \vee \overline c)) \rightarrow (c \wedge (b \vee a)) \)

Составьте таблицу истинности. В качестве ответа введите сумму значений \(c,\) при которых \(F = 1.\)

\[\begin{array}{|c|c|c|c|} \hline a & b & c & F\\\hline 0 & 0 & 0 & 1 \\ \hline 0 & 0 & 1 & 0 \\ \hline 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 \\ \hline 1 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 1 & 1 \\ \hline \end{array}\]

В таблице \(2^3 = 8\) строк.

1. Импликация ложна тогда и только тогда, когда из истинного высказывания следует ложное. Значит, \(F = 0,\) если a \(c \wedge (b \vee a) = 0.\) В остальных случаях \(F = 1.\) Рассмотрим, при каких значениях \(a,\) \(b\) и \(c\) \(a \equiv (b \vee \overline c) = 1\) (если \(a \equiv (b \vee \overline c) = 0,\) то \(F = 1\) при любом значении \(c \wedge (b \vee a) = 0).\)

Если \(a = 0,\) то, чтобы выполнялось \(a \equiv (b \vee \overline c) = 1,\) необходимо \(b \vee \overline c = 0\) (ведь операция эквивалентности истинна тогда и только тогда, когда оба высказывания истинны или оба ложны). Чтобы дизъюнкция \((b \vee \overline c)\) была ложна, оба высказывания, входящие в нее, должны быть ложны, то есть \(b = 0\) и \(\overline c = 0\) \((c = 1).\) При таких значениях \(c \wedge (b \vee a) = 1 \wedge (0 \vee 0) = 0.\) Тогда \((a \equiv (b \vee \overline c)) \rightarrow (c \wedge (b \vee a)) = 1 \rightarrow 0 = 0,\) \(F = 0.\) Это соответствует строке 2 из таблицы истинности.

Если \(a = 1,\) то чтобы выполнялось \(a \equiv (b \vee \overline c) = 1,\) \(b \vee \overline c = 1.\) Это выполняется в нескольких случаях. Если \(b = 1,\) то \(c\) может быть равна и нулю и единице, ведь одно из высказываний, входящих в дизъюнкцию, уже истинно. При \(c = 1\) \(c \wedge (b \vee a) = 1 \wedge 1 = 1,\) тогда \(F = 1\) (так как \(1 \rightarrow 1 = 1,\) строка 7). При \(c = 0\) \(c \wedge (b \vee a) = 0 \wedge 1 = 0,\) значит, \(F = 0\) \((1 \rightarrow 0 = 0,\) строка 6). Если \(b = 0,\) то \(\overline c = 1\) \((c = 0,\) тогда одно из высказываний, входящих в дизъюнкцию, будет истинным). В таком случае \(c \wedge (b \vee a) = 0 \wedge (0 \vee 1) = 0.\) \(F = 0,\) так как \(1 \rightarrow 0 = 0\) (строка 5).

2. При других значениях \(a,\) \(b\) и \(c\) \(F = 1,\) потому что \(a \equiv (b \vee \overline c) = 0\) (строки 1, 3, 7, 8).

3. Из составленной таблицы истинности видим, что \(F = 1\) при \(c = 0\) (строки 1, 4) и при \(c = 1\) (строки 3, 7, 8). Сумма значений равна 0 * 2 + 1 * 3 = 3.\(2^4 = 16\) строк.

1. Так как конъюнкция ложна, если ложно хотя бы одно из высказываний, то при \(d = 0\) \(F = 0\) при любых \(a,\) \(b\) и \(c\) (строки 1, 6-10, 12, 14 в таблице истинности).

2. Рассмотрим случай, когда \(d = 1.\) Тогда \((a \rightarrow b) \wedge (b \equiv c) \wedge d = (a \rightarrow b) \wedge (b \equiv c) \wedge 1 = (a \rightarrow b) \wedge (b \equiv c).\) При \(b = 1\) \(a \rightarrow b = a \rightarrow 1 = 1\) при любом \(a,\) так как импликация ложна тогда и только тогда, когда из истинного высказывания следует ложное. Если \(c = 1,\) то \(b \equiv c = 1,\) так как операция эквивалентности истинна, когда оба выражения истинны или оба ложны, и \(F = 1\) (так как все выражения, входящие в конъюнкцию, истинны). Это соответствует строкам 4 и 5. Если \(c = 0,\) то \(b \equiv c = 0,\) \(F = 0,\) так как одно из выражений, входящее в конъюнкцию, ложно (строки 11 и 16).

При \(b = 0:\) если \(a = 1,\) то \(a \rightarrow b = 1 \rightarrow 0 = 0,\) тогда одно из выражений, входящих в конъюнкцию, ложно, и \(F = 0\) при любом \(c\) (строки 13 и 15). Если \(a = 0,\) то \(a \rightarrow b = 0 \rightarrow 0 = 1.\) Если \(c = 0,\) то \(b \equiv c = 0 \equiv 0 = 1,\) \(F = 1,\) так как оба выражения, входящих в конъюнкцию, истинны (строка 2). Если \(c = 1,\) то \(b \equiv c = 0 \equiv 1 = 0,\) \(F = 0,\) так как одно из выражений, входящих в конъюнкцию, ложно (строка 3).

Таким образом, \(F = 1\) при \(d = 1\) (строки 2, 4, 5). Сумма значений \(d\) равна 1 * 3 = 3.

Таблица истинности - это таблица, которая описывает логическую функцию. Логическая функция здесь - это функция, у которой значения переменных и значение самой функции выражают истинность. Например, они принимают значения «истина» либо «ложь» (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 - эквивалентность

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

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

действия в скобках,
инверсия (отрицание ),
& (конъюнкция ),
v (дизъюнкция ),
=> (импликация ),
<=> (эквивалентность ).

Алгоритм составления таблицы истинности :

1. Выяснить количество строк в таблице (вычисляется как 2 n , где n – количество переменных + строка заголовков столбцов).

2. Выяснить количество столбцов (вычисляется как количество переменных + количество логических операций).

3. Установить последовательность выполнения логических операций.

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

5. Заполнить таблицу истинности по столбцам.

6. Записать ответ.

Пример 6

Построим таблицу истинности для выражения F =(Av B )&(¬ A v ¬ B ) .

1. Количество строк=2 2 (2 переменных+строка заголовков столбцов)=5.

2. Количество столбцов=2 логические переменные (А, В)+ 5 логических операций (v ,&, ¬ , v , ¬ ) = 7.

3. Расставим порядок выполнения операций: 1 5 2 43

(A v B ) & (¬ A v ¬ B )

4-5. Построим таблицу и заполним ее по столбцам:

6. Ответ: F =0, при A= B=0 и A= B=1

Пример 7

Построим таблицу истинности для логического выражения F = X v Y & ¬ Z .

1. Количество строк=2 3 +1=(3 переменных+строка заголовков столбцов)=9.

2. Количество столбцов=3 логические переменные+3 логических операций = 6.

3. Укажем порядок действий: 3 2 1

X v Y & ¬ Z

4-5. Построи м таблицу и заполним ее по столбцам:

			¬ Z	Y& ¬ Z	Xv Y & ¬ Z
0	0	0			0
0	0	1			0

6. Ответ:
F =0, при X= Y= Z= 0; при X= Y=0 и Z= 1.

Упражнение 8

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

1. F =(Av B )&(¬ A& ¬ B).

2. F = X&¬ Yv Z.

Проверьте себя (эталон ответов)

Обратите внимание!

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

А) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю единицами;

Б) разделить колонкузначенийвторой переменной на четыре части и заполнить каждую четверть чередующимися группами нулей и единиц, начиная с группы нулей;

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

Тавтология - тождественно истинная формула истина " ("1

Противоречие - тождественно ложная формула , или формула принимающая значение "ложь " ("0 ") при любых входящих в нее значениях переменных.

Равносильные формулы - две формулы А и В принимающие одинаковые значения, при одинаковых наборах значений входящих в них переменных. Равносильность двух формул алгебры логики обозначается символом .

Выбираем строки, где
и выписываем конъюнкции всех переменных, при чем, если переменная в этом наборе равна 1, то записываем ее саму, а если переменная = 0, то ее отрицание.

Для данного примера

коньюнкция этих дизъюнкций и будет искомой формулой:

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

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

Строго доказано, что любую формулу булевой алгебры можно выразить с помощью операций , &,. Интуитивно этот факт очевиден, вспомним алгоритм составления формулы по таблице истинности. При этом мы используем только эти операции. Такая форма записи называетсядизъюнктивной нормальной формой (ДНФ). Это своеобразный механизм нормализации формул алгебры логики.

Определение: ДНФ – это дизъюнкция различных элементарных конъюнкций (т.е. каждая конъюнкция состоит из элементарных высказываний или их отрицаний).

Аналогично определяется КНФ – коньюктивная нормальная форма.

Определение: Если в ДНФ все элементарные конъюнкции имеют один и тот же ранг, равный числу переменных, от которых зависит ДНФ, то она называетсясовершенной (СДНФ).

Теорема. Для любой функции, не являющейся тождественно ложной, существует и притом единственная СДНФ.

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

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

Системы {&,,}; {,}; {&,},{/} – являются функционально полными

{&,} – функционально неполная.

Мы примем эти факты без доказательства, и решая задачи, будем стараться любую формулу представить с помощью {&,,}. Позже мы более подробно обсудим вопрос функциональной полноты и неполноты системы операций.

(A v B )&(¬ A v ¬ B )

Рассмотрим пример решения логической задачи.

Пример :

После обсуждения состава участников экспедиции решено, что должны выполняться два условия.

Если поедет Арбузов, то должны ехать Брюквин или Вишневский

Если поедут Арбузов и Вишневский то поедет Брюквин

Составить логическую формулу принятия решения в символической форме, упростить полученную формулу и сформулировать по ней новое условие формирования экспедиции.

Введём переменные и соответствующие им элементарные высказывания.

- поедет Арбузов

- поедет Брюквин

- поедет Вишневский

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

Составим общую формулу и упростим выражение

т.е. если поедет Арбузов, то поедет Брюквин.

Пример:

Если завтра будет хорошая погода, то мы пойдем на пляж или поедем в лес. Составим формулу нашего поведения на завтра.

– хорошая погода

– мы пойдем на пляж

– мы поедем в лес

Теперь построим отрицание этой фразы

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

Желающие могут построить таблицу истинности и проверить это утверждение.

Пример :

По подозрению в совершенном преступлении, задержаны Браун, Джон и Смит. Один из них уважаемый в городе старик, второй чиновник, а третий известный мошенник. В ходе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом лгал.

Вот что они говорили:

Браун: Я совершил это. Джон не виноват. (Б&Д)

Джон: Браун не виноват. Преступник Смит. (Б&С)

Смит: Я не виноват. Виноват Браун (С&Б)

Опишем эти высказывания формально:

- преступление совершил Браун