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

Задание 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.

Построение таблиц истинности и логических функций

Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a , b ).

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

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

1. инверсия;

2. конъюнкция;

3. дизъюнкция;

4. импликация;

5. эквивалентность.

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

Алгоритм построения таблиц истинности для сложных выражений :

количество строк = 2 n + строка для заголовка ,

n - количество простых высказываний.

количество столбцов = количество переменных + количество логических операций ;

· определить количество переменных (простых выражений);

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

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

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

D = А & ( B V C )

Решение:

1. Определить количество строк:

на входе три простых высказывания: А, В, С поэтому n =3 и количество строк = 23 +1 = 9.

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

простые выражения (переменные): А, В, С ;

промежуточные результаты (логические операции):

А - инверсия (обозначим через E );

B V C - операция дизъюнкции (обозначим через F );

а также искомое окончательное значение арифметического выражения:

D = А & ( B V C ) . т. е. D = E & F - это операция конъюнкции.

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

font-size:12.0pt">Построение логической функции по ее таблице истинности:

Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции Z (X ,Y ):

font-size:12.0pt">1 .

Так как строки две, получаем дизъюнкцию двух элементов: () V () .

Каждый логический элемент в этой дизъюнкции запишем в виде конъюнкции аргументов функции X и Y : ( X & Y ) V ( X & Y ).

Алгебра логики

Алгебра логики

Алгебра логики (англ. algebra of logic ) — один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях.

Основоположником алгебры логики является английский математик и логик Дж. Буль (1815-1864), положивший в основу своего логического учения аналогию между алгеброй и логикой. Любое высказывание он записывал с помощью символов разработанного им языка и получал «уравнения», истинность или ложность которых можно было доказать, исходя из определенных логических законов, таких как законы коммутативности, дистрибутивности, ассоциативности и др.

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

Логическое высказывание — это любое повествовательное предложение, в отношении которого можно однозначно утверждать, что его содержание истинно или ложно.

Например, «3 умножить на 3 равно 9», «Архангельск севернее Вологды» — истинные высказывания, а «Пять меньше трех», «Марс — звезда» — ложные.

Очевидно, что не всякое предложение может быть логическим высказыванием, т. к. не всегда есть смысл говорить о его ложности или истинности. Например, высказывание «Информатика — интересный предмет» неопределенно и требует дополнительных сведений, а высказывание «Для ученика 10-А класса Иванова А. А. информатика — интересный предмет» в зависимости от интересов Иванова А. А. может принимать значение «истина» или «ложь».

Кроме двузначной алгебры высказываний , в которой принимаются только два значения — «истинно» и «ложно», существует многозначная алгебра высказываний. В такой алгебре, кроме значений «истинно» и «ложно», употребляются такие истинностные значения, как «вероятно», «возможно», «невозможно» и т. д.

В алгебре логики различаются простые (элементарные) высказывания , обозначаемые латинскими буквами (A, B, C, D, …), и сложные (составные), составленные из нескольких простых с помощью логических связок, например таких, как «не», «и», «или», «тогда и только тогда», «если … то» . Истинность или ложность получаемых таким образом сложных высказываний определяется значением простых высказываний.

Обозначим как А высказывание «Алгебра логики успешно применяется в теории электрических схем», а через В — «Алгебра логики применяется при синтезе релейно-контактных схем».

Тогда составное высказывание «Алгебра логики успешно применяется в теории электрических цепей и при синтезе релейно-контактных схем» можно кратко записать как А и В ; здесь «и» — логическая связка. Очевидно, что поскольку элементарные высказывания А и В истинны, то истинно и составное высказывание А и В .

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

Логических значений всего два: истина (TRUE) и ложь (FALSE) . Это соответствует цифровому представлению — 1 и 0 . Результаты каждой логической операции можно записать в виде таблицы. Такие таблицы называют таблицами истинности.

Основные операции алгебры логики

1. Логическое отрицание, инверсия (лат. inversion — переворачивание) — логическая операция, в результате которой из данного высказывания (например, А) получается новое высказывание (не А ), которое называется отрицанием исходного высказывания , обозначается символически чертой сверху ($A↖{-}$) или такими условными обозначениями, как ¬, "not" , и читается: «не А», «А ложно», «неверно, что А», «отрицание А» . Например, «Марс — планета Солнечной системы» (высказывание А); «Марс — не планета Солнечной системы» ($A↖{-}$); высказывание «10 — простое число» (высказывание В) ложно; высказывание «10 — не простое число» (высказывание B) истинно.

Операция, используемая относительно одной величины, называется унарной . Таблица значений данной операции имеет вид

Высказывание $A↖{-}$ ложно, когда А истинно, и истинно, когда А ложно.

Геометрически отрицание можно представить следующим образом: если А — это некоторое множество точек, то $A↖{-}$ — это дополнение множества А, т. е. все точки, которые не принадлежат множеству А.

2. Конъюнкция (лат. conjunctio — соединение) — логическое умножение, операция, требующая как минимум двух логических величин (операндов) и соединяющая два или более высказываний при помощи связки «и» (например, «А и В» ), которая символически обозначается с помощью знака ∧ (А ∧ В) и читается: «А и В». Для обозначения конъюнкции применяются также следующие знаки: А ∙ В; А & В, А and В , а иногда между высказываниями не ставится никакого знака: АВ. Пример логического умножения: «Этот треугольник равнобедренный и прямоугольный». Данное высказывание может быть истинным только в том случае, если выполняются оба условия, в противном случае высказывание ложно.

Высказывание А ∧ В истинно только тогда, когда оба высказывания — А и В истинны.

Геометрически конъюнкцию можно представить следующим образом: если А, В А ∧ В есть пересечение множеств А и В .

3. Дизъюнкция (лат. disjunction — разделение) — логическое сложение, операция, соединяющая два или более высказываний при помощи связки «или» (например, «А или В» ), которая символически обозначается с помощью знака ∨ (А ∨ В) и читается: «А или В» . Для обозначения дизъюнкции применяются также следующие знаки: А + В; А or В; А | B . Пример логического сложения: «Число x делится на 3 или на 5». Это высказывание будет истинным, если выполняются оба условия или хотя бы одно из условий.

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

Высказывание А ∨ В ложно только тогда, когда оба высказывания — А и В ложны.

Геометрически логическое сложение можно представить следующим образом: если А, В — это некоторые множества точек, то А ∨ В — это объединение множеств А и В , т. е. фигура, объединяющая и квадрат, и круг.

4. Дизъюнкция строго-разделительная, сложение по модулю два — логическая операция, соединяющая два высказывания при помощи связки «или» , употребленной в исключающем смысле, которая символически обозначается с помощью знаков ∨ ∨ или ⊕ (А ∨ ∨ В, А ⊕ В ) и читается: «либо А, либо В» . Пример сложения по модулю два — высказывание «Этот треугольник тупоугольный или остроугольный». Высказывание истинно, если выполняется какое-то одно из условий.

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

Высказывание А ⊕ В истинно только тогда, когда высказывания А и В имеют различные значения.

5. Импликация (лат. implisito — тесно связываю) — логическая операция, соединяющая два высказывания при помощи связки «если..., то» в сложное высказывание, которое символически обозначается с помощью знака → (А → В ) и читается: «если А, то В», «А влечет В», «из А следует В», «А имплицирует В» . Для обозначения импликации применяется также знак ⊃ (A ⊃ B). Пример импликации: «Если полученный четырехугольник квадрат, то около него можно описать окружность». Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием. Результат операции ложен только тогда, когда предпосылка есть истина, а следствие — ложь. Например, «Если 3 * 3 = 9 (А), то Солнце — планета (В)», результат импликации А → В — ложь.

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

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

6. Эквивалентность, двойная импликация, равнозначность (лат. aequalis — равный и valentis — имеющий силу) — логическая операция, позволяющая из двух высказываний А и В получить новое высказывание А ≡ В , которое читается: «А эквивалентно B» . Для обозначения эквивалентности применяются также следующие знаки: ⇔, ∼. Эта операция может быть выражена связками «тогда и только тогда», «необходимо и достаточно», «равносильно» . Примером эквивалентности является высказывание: «Треугольник будет прямоугольным тогда и только тогда, когда один из углов равен 90 градусам».

Таблица истинности операции эквивалентности имеет вид

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

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

Приоритет выполнения логических операций следующий: отрицание («не» ) имеет самый высокий приоритет, затем выполняется конъюнкция («и» ), после конъюнкции — дизъюнкция («или» ).

С помощью логических переменных и логических операций любое логическое высказывание можно формализовать, т. е. заменить логической формулой. При этом элементарные высказывания, образующие составное высказывание, могут быть абсолютно не связаны по смыслу, но это не мешает определять истинность или ложность составного высказывания. Например, высказывание «Если пять больше двух (А ), то вторник всегда наступает после понедельника (В )» — импликация А → В , и результат операции в данном случае — «истина». В логических операциях смысл высказываний не учитывается, рассматривается только их истинность или ложность.

Рассмотрим, например, построение составного высказывания из высказываний А и В , которое было бы ложно тогда и только тогда, когда оба высказывания истинны. В таблице истинности для операции сложения по модулю два находим: 1 ⊕ 1 = 0. А высказывание может быть, например, таким: «Этот мяч полностью красный или полностью синий». Следовательно, если утверждение А «Этот мяч полностью красный» — истина, и утверждение В «Этот мяч полностью синий» — истина, то составное утверждение — ложь, т. к. одновременно и красным, и синим мяч быть не может.

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

Пример 1. Определить для указанных значений X значение логического высказывания ((X > 3) ∨ (X < 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

Решение. Последовательность выполнения операций следующая: сначала выполняются операции сравнения в скобках, затем дизъюнкция, и последней выполняется операция импликации. Операция дизъюнкции ∨ ложна тогда и только тогда, когда оба операнда ложны. Таблица истинности для импликации имеет вид

Отсюда получаем:

1) для X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) для X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) для X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Пример 2. Указать множество целых значений X, для которых истинно выражение ¬((X > 2) → (X > 5)) .

Решение. Операция отрицания применена ко всему выражению ((X > 2) → (X > 5)) , следовательно, когда выражение ¬((X > 2) → (X > 5)) истинно, выражение ((X > 2) →(X > 5)) ложно. Поэтому необходимо определить, для каких значений X выражение ((X > 2) → (X > 5)) ложно. Операция импликации принимает значение «ложь» только в одном случае: когда из истины следует ложь. А это выполняется только для X = 3; X = 4; X = 5.

Пример 3. Для каких из приведенных слов ложно высказывание ¬(первая буква гласная ∧ третья буква гласная) ⇔ строка из 4 символов? 1) асса; 2) куку; 3) кукуруза; 4) ошибка; 5) силач.

Решение. Рассмотрим последовательно все предложенные слова:

1) для слова асса получим: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

2) для слова куку получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

3) для слова кукуруза получим: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 — высказывание ложно;

4) для слова ошибка получим: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 — высказывание истинно;

5) для слова силач получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 — высказывание ложно.

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

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

• выражения, которые используют операции сравнения («больше», «меньше», «равно», «не равно» и т. п.) и принимают логические значения (например, выражение а > b , где а = 5 и b = 7, равно значению «ложь»);
• непосредственные логические выражения, связанные с логическими величинами и логическими операциями (например, A ∨ В ∧ С, где А = истина, B = ложь и C = истина).

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

1. вычисление существующих функциональных зависимостей;
2. выполнение алгебраических операций (вначале умножение и деление, затем вычитание и сложение);
3. выполнение операций сравнения (в произвольном порядке);
4. выполнение логических операций (вначале операции отрицания, затем операции логического умножения, логического сложения, последними выполняются операции импликации и эквивалентности).

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

Пример. Найти значение выражения:

$1 ≤ a ∨ A ∨ sin(π/a - π/b) < 1 ∧ ¬B ∧ ¬(b^a + a^b > a + b ∨ A ∧ B)$ для а = 2, b = 3, A = истина, В = ложь.

Решение. Порядок подсчета значений:

1) b a + a b > a + b, после подстановки получим: 3 2 + 2 3 > 2 + 3, т. е. 17 > 2 + 3 = истина;

2) A ∧ B = истина ∧ ложь = ложь.

Следовательно, выражение в скобках равно (b a + a b > a + b ∨ A ∧ B) = истина ∨ ложь = истина;

3) 1≤ a = 1 ≤ 2 = истина;

4) sin(π/a - π/b) < 1 = sin(π/2 - π/3) < 1 = истина.

После этих вычислений окончательно получим: истина ∨ А ∧ истина ∧ ¬В ∧ ¬истина.

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

5) ¬В = ¬ложь = истина; ¬истина = ложь;

6) A ∧ истина ∧ истина ∧ ложь = истина ∧ истина ∧ истина ∧ ложь = ложь;

7) истина ∨ ложь = истина.

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

Примечание. Учитывая, что исходное выражение есть, в конечном итоге, сумма двух слагаемых, и значение одного из них 1 ≤ a = 1 ≤ 2 = истина, без дальнейших вычислений можно сказать, что результат для всего выражения тоже «истина».

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

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

Доказательства этих утверждений производят на основании построения таблиц истинности для соответствующих записей.

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

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

Рассмотрим на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

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

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .

Здесь для упрощения применяется закон поглощения.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

При преобразовании применяются правило де Моргана, операция переменной с ее инверсией, операция с константой

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

Пример 1. Найти логическое выражение, равносильное выражению A ∧ ¬(¬B ∨ C) .

Решение. Применяем правило де Моргана для В и С: ¬(¬B ∨ C) = B ∧ ¬C .

Получаем выражение, равносильное исходному: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Ответ: A ∧ B ∧ ¬C.

Пример 2. Указать значение логических переменных А, В, С, для которых значение логического выражения (A ∨ B) → (B ∨ ¬C ∨ B) ложно.

Решение. Операция импликации ложна только в случае, когд а из истинной посылки следует ложь. Следовательно, для заданного выражения посылка A ∨ B должна принимать значение «истина», а следствие, т. е. выражение B ∨ ¬C ∨ B , — «ложь».

1) A ∨ B — результат дизъюнкции — «истина», если хотя бы один из операндов — «истина»;

2) B ∨ ¬C ∨ B — выражение ложно, если все слагаемые имеют значение «ложь», т. е. В — «ложь»; ¬C — «ложь», а следовательно, переменная С имеет значение «истина»;

3) если рассмотреть посылку и учесть, что В — «ложь», то получим, что значение А — «истина».

Ответ: А — истина, В — ложь, С — истина.

Пример 3. Каково наибольшее целое число X, при котором истинно высказывание (35

Решение. Запишем таблицу истинности для операции импликации:

Выражение X < (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Ответ: X = 5.

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

Логические выражения могут быть использованы для описания геометрических областей. В этом случае задача формулируется так: записать для заданной геометрической области такое логическое выражение, которое принимает значение «истина» для значений x, y тогда и только тогда, когда любая точка с координатами (x; y) принадлежит геометрической области.

Рассмотрим описание геометрической области с помощью логического выражения на примерах.

Пример 1. Задано изображение геометрической области. Записать логическое выражение, описывающее множество точек, принадлежащих ей.

1) .

Решение. Заданную геометрическую область можно представить в виде набора следующих областей: первая область — D1 — полуплоскость ${x}/{-1} +{y}/{1} ≤ 1$, вторая — D2 — круг с центром в начале координат $x^2 + y^2 ≤ 1$. Их пересечение D1 $∩$ D2 представляет собой искомую область.

Результат: логическое выражение ${x}/{-1}+{y}/{1} ≤ 1 ∧ x^2 + y^2 ≤ 1$.

2)

Эту область можно записать так: |x| ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1 .

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

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

Пример 2. Нарисовать и заштриховать область, для точек которой выполняется логическое условие y ≥ x ∧ y + x ≥ 0 ∧ y < 2 .

Решение. Искомая область представляет собой пересечение трех полуплоскостей. Строим на плоскости (x, y) прямые y = x; y = -x; y = 2. Это границы области, причем последняя граница y = 2 не принадлежит области, поэтому ее наносим пунктирной линией. Для выполнения неравенства y ≥ x нужно, чтобы точки находились слева от прямой y = x, а неравенство y = -x выполняется для точек, которые находятся справа от прямой y = -x. Условие y < 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

Использование логических функций для описания электрических схем

Логические функции очень удобны для описания работы электрических схем. Так, для схемы, представленной на рис., где значение переменной X — это состояние выключателя (если он включен, значение X — «истина», а если выключен — «ложь»), это значение Y — это состояние лампочки (если она горит — значение «истина», а если нет — «ложь»), логическая функция запишется так: Y = X . Функцию Y называют функцией проводимости.

Для схемы, представленной на рис., логическая функция Y имеет вид: Y = X1 ∪ X2, т. к. достаточно одного включенного выключателя, чтобы горела лампочка. В схеме на рис., для того чтобы горела лампочка, должны быть включены оба выключателя, следовательно, функция проводимости имеет вид: Y = X1 ∧ X2 .

Для более сложной схемы функция проводимости будет иметь вид: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

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

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

Использование аппарата алгебры логики при проектировании логических схем

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера. Любая информация при обработке на компьютере представляется в двоичной форме, т. е. кодируется некоторой последовательностью 0 и 1. Обработку двоичных сигналов, соответствующих 0 и 1, выполняют в компьютере логические элементы. Логические элементы, которые выполняют основные логические операции И, ИЛИ, НЕ, представлены на рис.

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

Технически компьютерный логический элемент реализуется в виде электрической схемы, которая представляет собой соединение различных деталей: диодов, транзисторов, резисторов, конденсаторов. На вход логического элемента, который называют также вентилем, поступают электрические сигналы высокого и низкого уровней напряжения, на выход выдается один выходной сигнал также либо высокого, либо низкого уровня. Эти уровни соответствуют одному из состояний двоичной системы: 1 — 0; ИСТИНА — ЛОЖЬ. Каждый логический элемент имеет свое условное обозначение, которое выражает его логическую функцию, но не указывает на то, какая именно электронная схема в нем реализована. Это упрощает запись и понимание сложных логических схем. Работу логических схем описывают с помощью таблиц истинности. Условное обозначение на схеме ИЛИ знак «1» — от устаревшего обозначения дизъюнкции как «>=1» (значение дизъюнкции равно 1, если сумма двух операндов больше или равна 1). Знак «&» на схеме И является сокращенной записью английского слова and.

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

Построение таблиц истинности логических выражений

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

Удобной формой записи при нахождении значений функции является таблица, содержащая, кроме значений переменных и значений функции, также значения промежуточных вычислений. Рассмотрим пример построения таблицы истинности для формулы ${X1}↖{-} ∧ X2 ∨ {X1 ∨ X2}↖{-} ∨ X1$.

Если функция принимает значение 1 при всех наборах значений переменных, она является тождественно-истинной ; если при всех наборах входных значений функция принимает значение 0, она является тождественно-ложной ; если набор выходных значений содержит как 0, так и 1, функция называется выполнимой . Приведенный выше пример является примером тождественно-истинной функции.

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

1. Дизъюнктивно нормальная форма (ДНФ) — сумма произведений, образованных из переменных и их отрицаний для ложных значений.

Алгоритм построения ДНФ следующий:

1. в таблице истинности функции выбирают наборы аргументов, для которых логические формы равны 1 («истина»);
2. все выбранные логические наборы как логические произведения аргументов записывают, последовательно соединив их между собой операцией логической суммы (дизъюнкции);
3. для аргументов, которые являются ложными, в построенной записи проставляют операцию отрицания.

Пример. Построить функцию, определяющую, что первое число равно второму, используя метод ДНФ. Таблица истинности функции имеет вид

Решение. Выбираем наборы значений аргументов, в которых функция равна 1. Это первая и четвертая строки таблицы (строку заголовка при нумерации не учитываем).

Записываем логические произведения аргументов этих наборов, объединив их логической суммой: X1 ∧ X2 ∨ X1 ∧ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих ложное значение (четвертая строка таблицы; второй набор в формуле; первый и второй элементы): X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

Ответ: F(X1, X2) = X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

2. Конъюнктивно нормальная форма (КНФ) — произведение сумм, образованных из переменных и их отрицаний для истинных значений.

Алгоритм построения КНФ следующий:

1. в таблице истинности выбирают наборы аргументов, для которых логические формы равны 0 («ложь»);
2. все выбранные логические наборы как логические суммы аргументов записывают последовательно, соединив их между собой операцией логического произведения (конъюнкции);
3. для аргументов, которые являются истинными, в построенной записи проставляют операцию отрицания.

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

Пример 1. Рассмотрим предыдущий пример, т. е. построим функцию, определяющую, что первое число равно второму, используя метод КНФ. Для заданной функции ее таблица истинности имеет вид

Решение. Выбираем наборы значений аргументов, в которых функция равна 0. Это вторая и третья строки (строку заголовка при нумерации не учитываем).

Записываем логические суммы аргументов этих наборов, объединив их логическим произведением: X1 ∨ X2 ∧ X1 ∨ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих истинное значение (вторая строка таблицы, первый набор формулы, второй элемент; для третьей строки, а это второй набор формулы, первый элемент): X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2.

Таким образом, получена запись логической функции в КНФ.

Ответ: X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2.

Полученные двумя методами значения функций являются эквивалентными. Для доказательства этого утверждения используем правила логики: F(X1, X2) = X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2 = X1 ∧ ${X1}↖{-}$ ∨ X1 ∧ X2 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ ${X2}↖{-}$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ 0 = X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

Пример 2 . Построить логическую функцию для заданной таблицы истинности:

Искомая формула: X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ X2 .

Ее можно упростить: X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ X2 = X2 ∧ (X1 ∨ ${X1}↖{-}$) = X2 ∧ 1 = X2.

Пример 3. Для приведенной таблицы истинности построить логическую функцию, используя метод ДНФ.

Искомая формула: X1 ∧ X2 ∧ X ∨ ${X1}↖{-}$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ ${X3}↖{-}$ ∪ X1 ∧ ${X2}↖{-}$ ∧ ${X3}↖{-}$.

Формула достаточно громоздка, и ее следует упростить:

X1 ∧ X2 ∧ X3 ∨ ${X1}↖{-}$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ ${X3}↖{-}$ ∨ X1 ∧ ${X2}↖{-}$ ∧ ${X3}↖{-}$ = X2 ∧ X3 ∧ (X1 ∨ ${X1}↖{-}$) ∨ X1 ∧ ${X3}↖{-}$ ∧ (X2 ∨ ${X2}↖{-}$) = X2 ∧ X3 ∨ X1 ∧ ${X3}↖{-}$.

Таблицы истинности для решения логических задач

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

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

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

Решение. Очевидно, что результатом решения будет таблица, в которой искомая функция Y(X1, X2, X3) будет иметь значение «истина», если какие-либо две переменные имеют значение «истина».

Пример 2. Составить расписание уроков на день, учитывая, что урок информатики может быть только первым или вторым, урок математики — первым или третьим, а физики — вторым или третьим. Возможно ли составить расписание, удовлетворив всем требованиям? Сколько существует вариантов расписания?

Решение. Задача легко решается, если составить соответствующую таблицу:

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

1. математика, информатика, физика;
2. информатика, физика, математика.

Пример 3. В спортивный лагерь приехали трое друзей — Петр, Борис и Алексей. Каждый из них увлекается двумя видами спорта. Известно, что таких видов спорта шесть: футбол, хоккей, лыжи, плавание, теннис, бадминтон. Также известно, что:

1. Борис — самый старший;
2. играющий в футбол младше играющего в хоккей;
3. играющие в футбол и хоккей и Петр живут в одном доме;
4. когда между лыжником и теннисистом возникает ссора, Борис мирит их;
5. Петр не умеет играть ни в теннис, ни в бадминтон.

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

Решение. Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание.

Так как видов спорта шесть, получается, что все мальчики увлекаются разными видами спорта.

Из условия 4 следует, что Борис не увлекается ни лыжами, ни теннисом, а из условий 3 и 5, что Петр не умеет играть в футбол, хоккей, теннис и бадминтон. Следовательно, любимые виды спорта Петра — лыжи и плавание. Занесем это в таблицу, а оставшиеся клетки столбцов «Лыжи» и «Плавание» заполним нулями.

Из таблицы видно, что в теннис может играть только Алексей.

Из условий 1 и 2 следует, что Борис не футболист. Таким образом, в футбол играет Алексей. Продолжим заполнять таблицу. Внесем в пустые ячейки строки «Алексей» нули.

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

Ответ: Петр увлекается лыжами и плаванием, Борис играет в хоккей и бадминтон, а Алексей занимается футболом и теннисом.

Построение таблиц истинности сложных высказываний.

Приоритет логических операций

1) инверсия 2) конъюнкция 3) дизъюнкция 4) импликация и эквивалентность

Как составить таблицу истинности?

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

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

(0, 0), (0, 1), (1, 0), (1, 1).

Если формула содержит три переменные, то возможных наборов значений переменных восемь (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т. д.

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

Примеры.

1. Составим таблицу истинности для формулы 96%" style="width:96.0%">

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1 , то есть является тождественно истинной .

2. Таблица истинности для формулы 96%" style="width:96.0%">

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 0 , то есть является тождественно ложной .

3. Таблица истинности для формулы 96%" style="width:96.0%">

Из таблицы видно, что формула 0 " style="border-collapse:collapse;border:none">

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

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

Цели урока:

1. Обучающие:
   1. Научить составлять логические выражения из высказываний
   2. Ввести понятие “таблица истинности”
   3. Изучить последовательность действий построения таблиц истинности
   4. Научить находить значение логических выражений посредством построения таблиц истинности
   5. Ввести понятие равносильности логических выражений
   6. Научить доказывать равносильность логических выражений, используя таблицы истинности
   7. Закрепить навыки нахождения значений логических выражений посредством построения таблиц истинности
2. Развивающие:
   1. Развивать логическое мышление
   2. Развивать внимание
   3. Развивать память
   4. Развивать речь учащихся
3. Воспитательные:
   1. Воспитывать умение слушать учителя и одноклассников
   2. Воспитывать аккуратность ведения тетради
   3. Воспитывать дисциплинированность

Ход урока

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

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

Проверка домашнего задания

Записать решение домашних задач на доску
Все остальные откройте тетради, я пройду, проверю, как вы выполнили домашнее задание
Давайте еще раз повторим логические операции
В каком случае в результате операции логического умножения составное высказывание будет истинно?
Составное высказывание, образованное в результате операции логического умножения, истинно тогда и только тогда, когда истинны все входящие в него простые высказывания.
В каком случае в результате операции логического сложения составное высказывание будет ложно?
Составное высказывание, образованное в результате операции логического сложения, ложно тогда, когда ложны все входящие в него простые высказывания.
Как влияет инверсия на высказывание?
Инверсия делает истинное высказывание ложным и, наоборот, ложное – истинным.
Что вы можете сказать об импликации?
Логическое следование (импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если…, то…».
Обозначается А -> В
Составное высказывание, образованное с помощью операции логического следования (импли­кации), ложно тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод (второе высказывание).
Что вы можете сказать о логической операции эквивалентности?
Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота речи “... тогда и только тогда, когда…”, “…в том и только в том случае…”
Составное высказывание, образованное с помощью логической операции эквивалентности истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны.

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

Хорошо, повторили пройденный материал, переходим к новой теме.

На прошлом уроке мы находили значение составного высказы­вания путем подстановки исходных значений входящих логических переменных. А сегодня мы узнаем, что можно построить таблицу истинности, которая определяет истинность или лож­ность логического выражения при всех возможных комбинациях исходных значе­ний простых высказываний (логических переменных) и, что можно определить значения исходных логических переменных, зная какой нам нужен результат.

Еще раз рассмотрим наш пример с прошлого урока

и построим таблицу истинности для этого составного высказывания

При построении таблиц истинности есть определенная последовательность действий. Давайте запишем

1. Необходимо определить количество строк в таблице истинности.

• количество строк = 2 n , где n – количество логических переменных

Записали. Строим таблицу истинности
Что мы делаем во-первых?
Определить количество столбцов в таблице
Как мы это делаем?
Считаем количество переменных. В нашем случае логическая функция содержит 2 переменные
Какие?
А и В
Значит сколько строк будет в таблице?
Количество строк в таблице истинности должно быть равно 4.
А если 3 переменных?
Количество строк = 2³ = 8
Верно. Что делаем дальше?
Определяем количество столбцов = количеству логических переменных плюс количество логических операций.
Сколько будет в нашем случае?
В нашем случае количество переменных равно двум, а количество логических операции - пяти, то есть количество столбцов таблицы истинности равно семи.
Хорошо. Дальше?
Строим таблицу с указанным количеством строк и столбцов, обозначаем столбцы и вносим в таблицу возможные наборы значений исходных логических переменных и заполняем таблицу истинности по столбцам.
Какую операцию будем выполнять первой? Только учитывайте скобки и приоритеты
Можно сначала выполнить логическое отрицание или найти значение сначала в первой скобке, затем инверсию и значение во второй скобке, затем значение между этими скобками

Теперь мы можем определить значение логической функции для любого набора значении логических переменных
Теперь записываем пункт “Равносильные логические выражения”.
Логические выра­жения, у которых последние столбцы таблиц истинности сов­падают, называются равносильными. Для обозначения равносильных логических выражений используется знак “ = “,
Докажем, что логические выражения ┐ А& ┐В и AvB равносильны. Построим сначала таблицу истинности логического выражения

Сколько столбцов будет в таблице? 5
Какую операцию будем выполнять первой? Инверсию А, инверсию В

Теперь построим таблицу истинности логического выражения AvB
Сколько строк будет в таблице? 4
Сколько столбцов будет в таблице? 4

Мы все понимаем, что, если нужно найти отрицание для всего выражения, то приоритет, в нашем случае, принадлежит дизъюнкции. Поэтому сначала выполняем дизъюнкцию, а затем инверсию. К тому же мы можем переписать наше логическое выражение AvB. Т.к. нам нужно найти отрицание всего выражения, а не отдельных переменных, то инверсию можно вынести за скобки ┐(AvB), а мы знаем, что сначала находим значение в скобках

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

Решение задач

1.

Сколько переменных содержит данная формула? 3
Сколько строк и столбцов будет в таблице? 8 и 8
Какова будет в нашем примере последовательность операций? (инверсия, операции в скобках, операцию за скобкой)

2. Докажите с помощью таблиц истинности равносильность следую­щих логических выражений:

(А → B) И (Av┐B)

Какой делаем вывод? Данные логические выражения не равносильны

Домашнее задание

Доказать, используя таблицы истинности, что логические выражения

┐A v ┐B и А&В равносильны

Объяснение нового материала (продолжение)

Мы уже несколько уроков подряд используем понятие “таблица истинности”, а что же такое таблица истинности , как вы думаете?
Таблица истинности – это таблица, устанавливающая соответствие между возможными наборами значений логических переменных и значениями функций.
Как вы справились с домашним заданием, какой у вас получился вывод?
Выражения равносильны
Помните, на предыдущем уроке мы из составного высказывания составляли формулу, заменяя простые высказывания 2*2=4 и 2*2=5 переменными А и В
Теперь давайте учиться составлять логические выражения из высказываний

Запишите задание

Записать в виде логической формулы высказывания:

1) Если Иванов здоров и богат, то он здоров

Анализируем высказывание. Выявляем простые высказывания

А – Иванов здоров
В – Иванов богат

Хорошо, тогда как будет выглядеть формула? Только не забудьте, чтобы не терялся смысл высказывания, расставить скобки в формуле

2) Число является простым, если оно делится только на 1 и само на себя

А - число делится только на 1
В - число делится только на себя
С - число является простым

3) Если число делится на 4, оно делится на 2

А - делится на 4
В - делится на 2

4) Произвольно взятое число либо делится на 2,либо делится на 3

А - делится на 2
В - делится на 3

5) Спортсмен подлежит дисквалификации, если он некорректно ведет себя по отношению к сопернику или судье, и если он принимал «допинг».

А - спортсмен подлежит дисквалификации
В - некорректно ведет себя по отношению к сопернику
С - некорректно ведет себя по отношению к судье
D - принимал «допинг».

Решение задач

1. Построить таблицу истинности для формулы

((p&q)→ (p→ r)) v p

Объясняем сколько строк и столбцов будет в таблице? (8 и 7) Какова будет последовательность операций и почему?

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

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

2. Записать в виде логической формулы высказывания:

Администрация морского порта издала следующее распоряжение:

1. Если капитан корабля получает специальное указание, то он должен покинуть порт на своем корабле
2. Если капитан не получает специального указания, то он не должен покидать порт, или он впредь лишается допуска в этот порт
3. Капитан или лишается допуска в этот порт, или не получает специального указания

Выявляем простые высказывания, составляем формулы

• А - капитан получает специальное указание
• В - покидает порт
• С - лишается допуска в порт

1. ┐А→(┐В v С)
2. С v ┐А

3. Записать составное высказывание “(2*2=4 и 3*3 = 9) или (2*2≠4 и 3*3≠9)” в форме логического выражения. Построить таблицу истинности.

А={2*2=4} B={3*3 = 9}

(А&В) v (┐А&┐В)

Домашнее задание

Выбрать составное высказывание, имеющее ту же таблицу истинно­сти, что и не (не А и не (В и С)).

1. АиВ или СиА;
2. (А или В) и (А или С);
3. А и (В или С);
4. А или (не В или не С).