Определить логическую функцию по таблице истинности. Проверка домашнего задания
Задание 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.
Определение 1
Логическая функция – функция, переменные которой принимают одно из двух значений: $1$ или $0$.
Любую логическую функцию можно задать с помощью таблицы истинности: набор всех возможных аргументов записывается в левой части таблицы, а соответствующие значения логической функции – в правой части.
Определение 2
Таблица истинности – таблица, которая показывает, какие значения примет составное выражение при всех возможных наборах значений простых выражений, входящих в него.
Определение 3
Равносильными называются логические выражения, последние столбцы таблиц истинности которых совпадают. Равносильность обозначается с помощью знака $«=»$.
При составлении таблицы истинности важно учитывать следующий порядок выполнения логических операций:
Рисунок 1.
Приоритетом в выполнении порядка выполнения операций пользуются скобки.
Алгоритм построения таблицы истинности логической функции
Определяют количество строк: кол-во строк = $2^n + 1$ (для строки заголовка) , $n$ – количество простых выражений. Например, для функций двух переменных существует $2^2 = 4$ комбинации наборов значений переменных, для функций трех переменных – $2^3 = 8$ и т.д.
Определяют количество столбцов: кол-во столбцов = кол-во переменных + кол-во логических операций. При определении количества логических операций учитывают также порядок их выполнения.
Заполняют столбцы результатами выполнения логических операций в определенной последовательности, учитывая таблицы истинности основных логических операций.
Рисунок 2.
Пример 1
Составить таблицу истинности логического выражения $D=\bar{A} \vee (B \vee C)$.
Решение:
- инверсия ($\bar{A}$);
- дизъюнкция, т.к. она находится в скобках ($B \vee C$);
дизъюнкция ($\overline{A}\vee \left(B\vee C\right)$) – искомое логическое выражение.
Кол-во столбцов = $3 + 3=6$.
Определим количество строк:
кол-во строк = $2^3 + 1=9$.
Количество переменных – $3$.
Заполним таблицу, учитывая таблицы истинности логических операций.
Рисунок 3.
Пример 2
По данному логическому выражению построить таблицу истинности:
Решение:
- отрицание ($\bar{C}$);
- дизъюнкция, т.к. она находится в скобках ($A \vee B$);
- конъюнкция ($(A\vee B)\bigwedge \overline{C}$);
- отрицание, которое обозначим $F_1$ ($\overline{(A\vee B)\bigwedge \overline{C}}$);
- дизъюнкция ($A \vee C$);
- конъюнкция ($(A\vee C)\bigwedge B$);
- отрицание, которое обозначим $F_2$ ($\overline{(A\vee C)\bigwedge B}$);
дизъюнкция – искомая логическая функция ($\overline{(A\vee B)\bigwedge \overline{C}}\vee \overline{(A\vee C)\bigwedge B}$).
Определим количество строк:
Количество простых выражений – $n=3$, значит
кол-во строк = $2^3 + 1=9$.
Определим количество столбцов:
Количество переменных – $3$.
Количество логических операций и их последовательность:
Таблица истинности – таблица содержащая все возможные комбинации входных переменных и соответствующее им значения на выходе.
Таблица истинности содержит 2 n строк, где n – число входных переменных, и n+m – столбцы, где m – выходные переменные.
Инструкция
. При вводе с клавиатуры используйте следующие обозначения:
Например, логическое выражение abc+ab~c+a~bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Для ввода данных в виде логической схемы используйте этот сервис .
Правила ввода логической функции
- Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
- Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
- Максимальное количество переменных равно 10 .
Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики - алгебры логики. В алгебре логики можно выделить три основные логические функции: "НЕ" (отрицание), "И" (конъюнкция), "ИЛИ" (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2 n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:
- словесное описание – это форма, которая используется на начальном этапе проектирования имеет условное представление.
- описание функции алгебры логики в виде таблицы истинности.
- описание функции алгебры логики в виде алгебраического выражения: используется две алгебраические формы ФАЛ:
а) ДНФ – дизъюнктивная нормальная форма – это логическая сумма элементарных логических произведений. ДНФ получается из таблицы истинности по следующему алгоритму или правилу:
1) в таблице выбираются те строки переменных для которых функция на выходе =1 .
2) для каждой строки переменных записывается логическое произведение; причём переменные =0 записываются с инверсией.
3) полученное произведение логически суммируется.
Fднф= X 1 *Х 2 *Х 3 ∨ Х 1 x 2 Х 3 ∨ Х 1 Х 2 x 3 ∨ Х 1 Х 2 Х 3
ДНФ называется совершенной, если все переменные имеют одинаковый ранг или порядок, т.е. в каждое произведение обязательно должны включаться все переменные в прямом или инверсном виде.
б) КНФ – конъюнктивная нормальна форма – это логическое произведение элементарных логических сумм.
КНФ может быть получена из таблицы истинности по следующему алгоритму:
1) выбираем наборы переменных для которых функция на выходе =0
2) для каждого набора переменных записываем элементарную логическую сумму, причём переменные =1 записываются с инверсией.
3) логически перемножаются полученные суммы.
Fскнф=(X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
КНФ называется совершенной , если все переменные имеют одинаковый ранг.
Рисунок1- Схема логического устройства
Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможны х логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.
Операция НЕ - логическое отрицание (инверсия)
Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:- если исходное выражение истинно, то результат его отрицания будет ложным;
- если исходное выражение ложно, то результат его отрицания будет истинным.
не А, Ā, not A, ¬А, !A
Результат операции отрицания НЕ определяется следующей таблицей истинности:
| A | не А |
| 0 | 1 |
| 1 | 0 |
Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот.
Операция ИЛИ - логическое сложение (дизъюнкция, объединение)
Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.Применяемые обозначения: А или В, А V В, A or B, A||B.
Результат операции ИЛИ определяется следующей таблицей истинности:
Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В - ложны.
Операция И - логическое умножение (конъюнкция)
Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.Применяемые обозначения: А и В, А Λ В, A & B, A and B.
Результат операции И определяется следующей таблицей истинности:
| A | B | А и B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях.
Операция «ЕСЛИ-ТО» - логическое следование (импликация)
Эта операция связывает два простых логических выражения, из которых первое является условием, а второе - следствием из этого условия.Применяемые обозначения:
если А, то В; А влечет В; if A then В; А→ В.
Таблица истинности:
| A | B | А → B |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.
Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)
Применяемое обозначение: А ↔ В, А ~ В.Таблица истинности:
| A | B | А↔B |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)
Применяемое обозначение: А XOR В, А ⊕ В.Таблица истинности:
| A | B | А⊕B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.
Приоритет логических операций
- Действия в скобках
- Инверсия
- Конъюнкция (&)
- Дизъюнкция (V), Исключающее ИЛИ (XOR), сумма по модулю 2
- Импликация (→)
- Эквивалентность (↔)
Совершенная дизъюнктивная нормальная форма
Совершенная дизъюнктивная нормальная форма формулы (СДНФ) это равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, обладающая свойствами:- Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
- Все логические слагаемые формулы различны.
- Ни одно логическое слагаемое не содержит переменную и её отрицание.
- Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.
Для каждой функции СДНФ и СКНФ определены единственным образом с точностью до перестановки.
Совершенная конъюнктивная нормальная форма
Совершенная конъюнктивная нормальная форма формулы (СКНФ) это равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций, удовлетворяющая свойствам:- Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
- Все элементарные дизъюнкции различны.
- Каждая элементарная дизъюнкция содержит переменную один раз.
- Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.
В цифровой схемотехнике цифровой сигнал - это сигнал, который может принимать два значения, рассматриваемые как логическая "1" и логический "0".
Логические схемы могут содержать до 100 миллионов входов и такие гигантские схемы существуют. Представьте себе, что булева функция (уравнение) такой схемы была потеряна. Как восстановить её с наименьшими потерями времени и без ошибок? Наиболее продуктивный способ - разбить схему на ярусы. При таком способе записывается выходная функция каждого элемента в предыдущем ярусе и подставляется на соответствующий вход на следующем ярусе. Этот способ анализа логических схем со всеми нюансами мы сегодня и рассмотрим.
Логические схемы реализуются на логических элементах: "НЕ", "И", "ИЛИ", "И-НЕ", "ИЛИ-НЕ", "Исключающее ИЛИ" и "Эквивалентность". Первые три логических элемента позволяют реализовать любую, сколь угодно сложную логическую функцию в булевом базисе . Мы будем решать задачи на логические схемы, реализованные именно в булевом базисе.
Для обозначения логических элементов используется несколько стандартов. Наиболее распространёнными являются американский (ANSI), европейский (DIN), международный (IEC) и российский (ГОСТ). На рисунке ниже приведены обозначения логических элементов в этих стандартах (для увеличения можно нажать на рисунок левой кнопкой мыши).
На этом уроке будем решать задачи на логические схемы, на которых логические элементы обозначены в стандарте ГОСТ.
Задачи на логические схемы бывают двух видов: задача синтеза логических схемы и задачи анализа логических схем. Мы начнём с задачи второго типа, так как в таком порядке удаётся быстрее научиться читать логические схемы.
Чаще всего в связи с построением логических схем рассматриваются функции алгебры логики:
- трёх переменных (будут рассмотрены в задачах анализа и в одной задаче синтеза);
- четырёх переменных (в задачах синтеза, то есть в двух последних параграфах).
Рассмотрим построение (синтез) логических схем
- в булевом базисе "И", "ИЛИ", "НЕ" (в предпоследнем параграфе);
- в также распространённых базисах "И-НЕ" и "ИЛИ-НЕ" (в последнем параграфе).
Задача анализа логических схем
Задача анализа заключается в определении функции f , реализуемой заданной логической схемой. При решении такой задачи удобно придерживаться следующей последовательности действий.
- Логическая схема разбивается на ярусы. Ярусам присваиваются последовательные номера.
- Выводы каждого логического элемента обозначаются названием искомой функции, снабжённым цифровым индексом, где первая цифра - номер яруса, а остальные цифры - порядковый номер элемента в ярусе.
- Для каждого элемента записывается аналитическое выражение, связывающее его выходную функцию с входными переменными. Выражение определяется логической функцией, реализуемой данным логическим элементом.
- Производится подстановка одних выходных функций через другие, пока не получится булева функция, выраженная через входные переменные.
Пример 1.
Решение. Разбиваем логическую схему на ярусы, что уже показано на рисунке. Запишем все функции, начиная с 1-го яруса:
x , y , z :
| x | y | z | f | ||||
| 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
Пример 2. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Пример 3. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Продолжаем искать булеву функцию логической схемы вместе
Пример 4. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Решение. Разбиваем логическую схему на ярусы. Запишем все функции, начиная с 1-го яруса:
Теперь запишем все функции, подставляя входные переменные x , y , z :
В итоге получим функцию, которую реализует на выходе логическая схема:
.
Таблица истинности для данной логической схемы:
| x | y | z | f | ||
| 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 |
Пример 5. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.
Решение. Разбиваем логическую схему на ярусы. Структура данной логической схемы, в отличие от предыдущих примеров, имеет 5 ярусов, а не 4. Но одна входная переменная - самая нижняя - пробегает все ярусы и напрямую входит в логический элемент в первом ярусе. Запишем все функции, начиная с 1-го яруса:
Теперь запишем все функции, подставляя входные переменные x , y , z :
В итоге получим функцию, которую реализует на выходе логическая схема:
.
Таблица истинности для данной логической схемы:
| x | y | z | f | ||
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 1 |
Задача синтеза логических схем в булевом базисе
Разработка логической схемы по её аналитическому описанию имеет название задачи синтеза логической схемы.
Каждой дизъюнкции (логической сумме) соответствует элемент "ИЛИ", число входов которого определяется количеством переменных в дизъюнкции. Каждой конъюнкции (логическому произведению) соответствует элемент "И", число входов которого определяется количеством переменных в конъюнкции. Каждому отрицанию (инверсии) соответствует элемент "НЕ".
Часто разработка логической схемы начинается с определения логической функции, которую должна реализовать логическая схемы. В этом случае дана только таблица истинности логической схемы. Мы разберём именно такой пример, то есть, решим задачу, полностью обратную рассмотренной выше задаче анализа логических схем.
Пример 6. Построить логическую схему, реализующую функцию с данной таблицей истинности.
Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль . Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a, b) .
Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записывается набор аргументов, а в правой части - соответствующие значения логической функции. При построении таблицы истинности необходимо учитывать порядок выполнения логических операций.
Порядок выполнения логических операций в сложном логическом выражении:
1. инверсия;
2. конъюнкция;
3. дизъюнкция;
4. импликация;
5. эквивалентность.
Для изменения указанного порядка выполнения операций используются скобки.
Для каждого составного высказывания (логического выражения) можно построить таблицу истинности , которая определяет его истинность или ложность при всех возможных комбинациях исходных значений простых высказываний (логических переменных).
При построении таблицы истинности целесообразно руководствоваться определенной последовательностью действий.
Алгоритм построения таблиц истинности для сложных выражений:
количество строк = 2 n + строка для заголовка ,
n - количество простых высказываний.
количество столбцов = количество переменных + количество логических операций ;
o определить количество переменных (простых выражений);
o определить количество логических операций и последовательность их выполнения.
3. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.
Пример: Составить таблицу истинности логического выражения:
D = А & (B C) .
Решение:
1. Определить количество строк:
на входе три простых высказывания: А, В, С поэтому n=3 и количество строк = 2 3 +1 = 9.
2. Определить количество столбцов:
o простые выражения (переменные): А, В, С ;
o промежуточные результаты (логические операции):
o А - инверсия (обозначим через E );
o B C - операция дизъюнкции (обозначим через F );
o а также искомое окончательное значение арифметического выражения:
o D = А & (B C) . т.е. D = E & F - это операция конъюнкции.
3. Заполнить столбцы с учетом таблиц истинности логических операций.
Составить логическую функцию для заданной таблицы истинности.
Правила построения логической функции по ее таблице истинности:
1. Выделить в таблице истинности те строки, в которых значение функции равно 1 .
2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.
3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.
4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0 , то этот аргумент взять с отрицанием.
Решение.
1. В первой и третьей строках таблицы истинности значение функции равно 1 .
2. Так как строки две, получаем дизъюнкцию двух элементов: () V () .
3. Каждый логический элемент в этой дизъюнкции запишим в виде конъюнкции аргументов функции X и Y : (X & Y) V (X & Y) .
4. Берем аргумент с отрицанием если его значение в соответствующей строке таблицы равно 0 и получаем искомую функцию:
5. Z (X, Y) =(X & Y) V (X & Y) .
Пример 4. Определить участника преступления, исходя из двух посылок:
1) "Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал";
2) 2) "Если Иванов не участвовал, то Сидоров не участвовал".
Решение
Составим выражения:
I - "Иванов участвовал в преступлении";
P - "Петров участвовал в преступлении";
S - "Сидоров участвовал в преступлении".
Запишем посылки в виде формул:
Проверим результат, используя таблицу истинности:
Ответ: Иванов участвовал в преступлении.
Количество входных переменных в заданном выражении равно трем (A,B,C) . Значит, количество входных наборов Q=2 3 =8 .
Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C , промежуточных результатов и (B V C ), а также искомого окончательного значения сложного арифметического выражения :
| A | B | C | B V C | ||
Загрузка...
