Как составить таблицу значений логической функции - Сайт, где вы сможете решить свои вопросы

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

Екатерина Андреевна Гапонько

Эксперт по предмету «Информатика»

Задать вопрос автору статьи

Определение 1

Логическая функция – функция, переменные которой принимают одно из двух значений: $1$ или $0$.

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

Определение 2

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

Определение 3

Равносильными называются логические выражения, последние столбцы таблиц истинности которых совпадают. Равносильность обозначается с помощью знака $«=»$.

Сдай на права пока
учишься в ВУЗе

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

Получить скидку 3 000 ₽

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

Рисунок 1.

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

Алгоритм построения таблицы истинности логической функции

Определяют количество строк: кол-во строк = $2^n + 1$ (для строки заголовка), $n$ – количество простых выражений. Например, для функций двух переменных существует $2^2 = 4$ комбинации наборов значений переменных, для функций трех переменных – $2^3 = 8$ и т.д.
Определяют количество столбцов: кол-во столбцов = кол-во переменных + кол-во логических операций. При определении количества логических операций учитывают также порядок их выполнения.
Заполняют столбцы результатами выполнения логических операций в определенной последовательности, учитывая таблицы истинности основных логических операций.

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

Рисунок 2.

Пример 1

Составить таблицу истинности логического выражения $D=bar{A} vee (B vee C)$.

Решение:

Определим количество строк:

Количество простых выражений – $n=3$, значит

кол-во строк = $2^3 + 1=9$.
Определим количество столбцов:

Количество переменных – $3$.

Количество логических операций и их последовательность:
1. инверсия ($bar{A}$);
2. дизъюнкция, т.к. она находится в скобках ($B vee C$);
3. дизъюнкция ($overline{A}vee left(Bvee Cright)$) – искомое логическое выражение.
  
  Кол-во столбцов = $3 + 3=6$.
Заполним таблицу, учитывая таблицы истинности логических операций.

Рисунок 3.

Пример 2

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

[F=overline{(Avee B)bigwedge overline{C}}vee overline{(Avee C)bigwedge B}]

Решение:

Определим количество строк:

Количество простых выражений – $n=3$, значит

кол-во строк = $2^3 + 1=9$.
Определим количество столбцов:

Количество переменных – $3$.

Количество логических операций и их последовательность:
1. отрицание ($bar{C}$);
2. дизъюнкция, т.к. она находится в скобках ($A vee B$);
3. конъюнкция ($(Avee B)bigwedge overline{C}$);
4. отрицание, которое обозначим $F_1$ ($overline{(Avee B)bigwedge overline{C}}$);
5. дизъюнкция ($A vee C$);
6. конъюнкция ($(Avee C)bigwedge B$);
7. отрицание, которое обозначим $F_2$ ($overline{(Avee C)bigwedge B}$);
8. дизъюнкция – искомая логическая функция ($overline{(Avee B)bigwedge overline{C}}vee overline{(Avee C)bigwedge B}$).
  
  Кол-во столбцов = $3 + 8 = 11$.
Заполним таблицу, учитывая таблицу истинности логических операций.

Рисунок 4.

Алгоритм построения логической функции по ее таблице истинности

Выделяют в таблице истинности строки со значением функции, равным $1$.
Выписывают искомую формулу как дизъюнкцию нескольких логических выражений. Количество этих выражений равно количеству выделенных строк.
Каждое логическое выражение в этой дизъюнкции записать как конъюнкцию аргументов функции.
В случае, когда значение какого-то из аргументов функции в соответствующей строке таблицы принимает значение $0$, то этот аргумент записать в виде его отрицания.

Пример 3

По данной таблице истинности некоторой логической функции $Y(A,B)$ cоставить соответствующую логическую функцию.

Рисунок 5.

Решение:

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

Рисунок 6.
Каждое логическое выражение в этой дизъюнкции запишем как конъюнкцию аргументов функции $A$ и $B$: $left(Awedge Bright)vee left(Awedge Bright)$
В случае, когда значение в соответствующей строке таблицы равно $0$, запишем этот аргумент с отрицанием, получим искомую функцию:[Yleft(A,Bright)=left(overline{A}wedge overline{B}right)vee left(Awedge overline{B}right).]

Находи статьи и создавай свой список литературы по ГОСТу

Поиск по теме

Дата написания статьи: 12.04.2016

Источник

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

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

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

Определения 1 — 2

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

Равносильными именуют те логические выражения с совпадающими последними столбцами таблицы истинности. Обозначают равносильные функции знаком «=».

Правила того, как следует проводить построение таблицы истинности

Несоблюдение хотя бы одного из них ведёт к очень грубой ошибке. Вот эти правила:

Число строк таблицы должно совпадать с числом комбинаций всевозможных n логических переменных, то есть быть равным 2ⁿ;
Количество столбцов таблицы должно равняться сумме числа логических переменных и числа логических операций;
В построенный шаблон таблицы истинности должны вписываться все значения исходных переменных;
Построение таблицы истинности выражения происходит по её столбцам, при этом обязательно учитываются правила логических операций.

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

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

Определить, какое число строк и столбцов будет в будущей таблице. Делается подобное по формулам
X = n + m, Y = 2ⁿ+1.
Где n – число переменных, m – чило логических операций.
Заполнить самую верхнюю строку таблицы переменными и логическими операциями, идя слева направо. При этом приоритетность логических операций следует учитывать обязательно, иначе получится совсем не то, что нужно;
В первых столбцах перечислить всевозможные комбинации входных значений;
Выполняя заданные логические операции, заполнить все оставшиеся ячейки;

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

О порядке логических операций

Лучше его представить списком. Логические операции выполняют в следующей последовательности: сначала идёт инверсия, затем конъюнкция, после этого дизъюнкция, после неё импликация, по её выполнении эквиваленция.

После них идут Штрих Шеффера и Стрелка Пирса. Первым может быть выполнено как то, так и другое.

Далее приведём несколько поучительных задач на построение таблиц истинности

Задачи 1 — 3

Сделать построение таблицы истинности для функции ((A→B) ∧ A) ↔ B

Решение:

1. Определяем сколько будет у нас столбцов. Количество переменных у нас 2, логических операций 4, число столбцов равно сумме 2+4 = 6.
2. Определяем, сколько будет у на строк. Оно равно 2ⁿ, плюс ещё одна строка для обозначения переменных и логических операций. У нас будет 2ⁿ+1 = 2² + 1= 5;
3. Заполняем первую строку. Прописываем символы переменные и логических операций;
4. В двух первых столбцах записываем возможные значения переменных;
5. В далее идущих столбцах записываем, какие значения принимают промежуточные функции;
6. В самом последнем из столбцов записываем итоговые значения функции.

В результате всего этого у нас должно получиться:

Провести построение таблицы истинности функции (A ∨ B) ∧ – C

Решение:

Определяем сколько будет столбцов. Количество переменных у нас 3, количество логических операций 3. Складываем то и другое: 3+3 = 5.
Определяем, количество строк. Оно равно 2n, плюс ещё одна строка для обозначения переменных и логических операций.В итоге будет 2n+1 = 2³ + 1= 9;

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

В итоге получим таблицу:

Сделать таблицу истинности для

(A ∧ B ↔ B ∧ C) ∨ (C → A)

Функция посложнее и таблица получится значительно больше, чем предыдущая.

Считаем столбцы. Количество переменных 3, количество логических операций 6. Значит столбцов будет 3+6=9;
Считаем строки. Их количество будет 2³+1= 9;
Заполняем первую строку таблицы;
В первых столбцах записываем все допустимые значения наших переменных;
В остающихся столбцах пишем, какие наша функция принимает промежуточные значения
В последний столбец пишем итоговые значения данной нам функции.

В итоге у нас получается таблица:

Нет времени решать самому?

Наши эксперты помогут!

Построения функции, если известна её таблица истинности

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

Алгоритм действий для получения СДНФ по таблице истинности:

Отметьте в таблице строки, в которых значение функции равняется 1
Выпишете для каждой отмеченной строки конъюкцию всех переменных. Если переменная равна 1, в конъюкцию следует включить саму эту переменную. Если переменная равняется 0, то её отрицание;
Все полученные конъюкции свяжите в дизъюкцию.

Аналогичным образом определяется СКНФ

В строках, в последнем столбце которых функция равна 0, запишите дизъюкции всех переменных. Если значение переменной в данной строке будет 0, в дизъюкцию следует включить саму эту переменную. Если значение функции равно 1, то включить нужно её отрицание.

Правило + задача

СДНФ всегда равно СКНФ. СДНФ = СКНФ.

Дана таблица истинности:

Выделяем в ней цветом строку

Заполняем столбцы с СДНФ и с СКНФ

Записываем СДНФ

СДНФ = A & B

Записываем СКНФ

СКНФ = (A ∨ B) & (A ∨ B) & (A ∨ B)

Источник

дана функция:

F=(X∨Y)∧¬Z

Необходимо построить таблицу истинности.

Будем действовать согласно приведённому выше алгоритму.

1. Количество переменных — (3) (X, Y, Z); количество логических операций — (3).

Количество столбцов (=) (3 + 3 = 6); количество строк (=)

23=8

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

3. Перечислим все возможные значения входных данных. Для того чтобы не пропустить ни одного значения, используют следующее правило: в значение первой переменной записывают (4) нуля, затем (4) единицы, в значении второй переменной чередуют (2) нуля и (2) единицы, а значение третьей переменной — чередование (0) и (1).

4. Заполним ячейки таблицы, выполняя логические операции.

(X)	(Y)	(Z)	X∨Y	¬Z	(F)
(0)	(0)	(0)	(0)	(1)	(0)
(0)	(0)	(1)	(0)	(0)	(0)
(0)	(1)	(0)	(1)	(1)	(1)
(0)	(1)	(1)	(1)	(0)	(0)
(1)	(0)	(0)	(1)	(1)	(1)
(1)	(0)	(1)	(1)	(0)	(0)
(1)	(1)	(0)	(1)	(1)	(1)
(1)	(1)	(1)	(1)	(0)	(0)

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

F=(X∨Y)∧¬Z

принимает истинные или ложные значения.

Источник

Логические выражения и таблица истинности

Примеры задач с решениями по этой теме Пройти тестирование по теме Контрольная по теме

Таблица истинности — таблица, показывающая, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний.

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

Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак «=».

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

1. подсчитать количество переменных n в логическом выражении;

2. определить число строк в таблице по формуле m=2ⁿ, где n — количество переменных;

3. подсчитать количество логических операций в формуле;

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

5. определить количество столбцов: число переменных + число операций;

6. выписать наборы входных переменных;

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

Заполнение таблицы:

1. разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»;

2. разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»;

3. продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа.

Пример 1. Для формулы A/ (B / ¬B /¬C) постройте таблицу истинности.

Количество логических переменных 3, следовательно, количество строк — 2³ = 8.

Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов — 3 + 5 = 8.

Пример 2. Определите истинность логического выражения F(А, В) = (А/ В)/(¬А/¬В) .

1. В выражении две переменные А и В (n=2).

2. m_строк=2ⁿ, m=2²=4 строки.

3. В формуле 5 логических операций.

4. Расставляем порядок действий

1) А/ В; 2) ¬А; 3) ¬В; 4) ¬А/¬В; 5) (А/ В)/(¬А/¬В).

5. К_{столбцов}=n+5=2+5=7 столбцов.

А	В	А/ В	¬А	¬В	¬А/¬В	F
0	0	0	1	1	1	0
0	1	1	1	0	1	1
1	0	1	0	1	1	1
1	1	1	0	0	0	0

Вывод: логическое выражение принимает значение истина при наборах F(0,1)=1 и F(1,0)=1.

Пример 3. Построёте таблицу истинности для логического выражения

F = (A/ B) / ¬С

В данной функции три логические переменные – А, В, С
количество строк таблицы = 2³=8
В формуле 3 логические операции.
Расставляем порядок действий

1) А/ В; 2) ¬С; 3) (AVB) / ¬С .

количество столбцов таблицы = 3 + 3 = 6

А	В	С	A/B	¬С	(A/B) / ¬С
0	0	0	0	1	0
0	0	1	0	0	0
0	1	0	1	1	1
0	1	1	1	0	0
1	0	0	1	1	1
1	0	1	1	0	0
1	1	0	1	1	1
1	1	1	1	0	0

Пример 4. Определите истинность формулы: F = ((С /В) => В) / (А / В) => В.

Построим таблицу истинности этой формулы.

Ответ: формула является тождественно истинной.

Пример 5. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.

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

X	Y	Z	F
0	0	0	1
0	0	1	0
0	1	0	1

Какое выражение соответствует F?

1) ¬X/¬Y/Z 2) ¬X/¬Y/Z 3) X/Y/¬Z 4) X/Y/Z

Решение (вариант 1, через таблицы истинности):

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

X	Y	Z	F	¬X	¬Y	¬Z	¬X/¬Y/Z	¬X/¬Y/Z	X/Y/¬Z	X/Y/Z
0	0	0	1	1	1	1	0	1	1	0
0	0	1	0	1	1	0	1	1	0	1
0	1	0	1	1	0	1	0	1	1	1

Очевидно, что значения заданной функции F совпадают со значениями выражения X/Y/¬Z. Следовательно, правильный ответ – 3.

Ответ: 3

Решение (Вариант 2):

Чтобы не строить таблицу истинности для каждого выражения, можно просто перепроверить предложенные ответы по заданной таблице истинности. Т.е. в каждую из четырех предложенных функций последовательно подставлять значения переменных X, Y и Z, из заданной таблицы истинности и вычислять значения логического выражения. Если значения вычисляемого выражения совпадут со значением F во всех трех строчках заданной таблицы, то это и есть искомое выражение.

Рассмотрим данный конкретный пример:

1) первое заданное выражение ¬X/¬Y/Z = 0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы;

2) второе заданное выражение ¬X/¬Y/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы;

3) третье выражение X/Y/¬Z соответствует F при всех предложенных комбинациях X,Y и Z;

4) четвертое выражение X/Y/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.

Ответ: 3

Источник

Теория:

Алгеброй
называется множество с определенными
на нем операциями. Обычно, алгебра
задается следующей парой: (Ω;M),
где M
– множество элементов алгебры; Ω –
сигнатура, включающая в себя множество
операций над элементами алгебры.

Алгеброй
логики называется алгебра, в которой М
– множество логических переменных и
функций, а Ω имеет следующий вид:

Ω={,,,,
/, ~,,}

Функцией
алгебры логики (логической функцией
или булевой функцией) называется функция,
аргументы которой и ее значения могут
принимать значения из двух-элементарного
множества. (Чаще всего это множества,
содержащие 0 и 1)

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

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

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

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

Конъюнкция:

X₁	X₂	X₁X₂
0	0	0
0	1	0
1	0	0
1	1	1

Конъюнкцию
называют также логическим умножением.

Конъюнкция
обозначается также A*B
или
A&B
.

Дизъюнкция:

X₁	X₂	X₁X₂
0	0	0
0	1	1
1	0	1
1	1	1

Дизъюнкция
обозначается также A+B
.

Сложение
по модулю два (неравнозначность):

X₁	X₂	X₁X₂
0	0	0
0	1	1
1	0	1
1	1	0

Неравнозначность
называют также суммой по модулю 2, суммой
Жегалкина, прямой суммой, строгой

дизъюнкцией.

Импликация
(следование):

X₁	X₂	X₁X₂
0	0	1
0	1	1
1	0	0
1	1	1

Импликацию
называют также следуемостью.

Импликация
обозначается также ABили
A
B
.

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

X₁	X₂	X1~X2
0	0	1
0	1	0
1	0	0
1	1	1

Эквиваленцию
двух высказываний называют также
равнозначностью, равносильностью,
тождественностью.

Эквиваленция
обозначается также A
=
B
или
ABили
A~
B
.

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

X₁	X₂	X₁X₂
0	0	1
0	1	0
1	0	0
1	1	0

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

X₁	X₂	X₁X₂
0	0	1
0	1	1
1	0	1
1	1	0

Отрицание:

X
0	1
1	0

Иерархия
булевых функций:

действия
в скобках,

отрицание,

конъюнкция,

дизъюнкция,

неравнозначеность,

эквиваленция,

импликация

(операции,
стоящие на одном уровне, при отсутствии
скобок выполняются в порядке их появления
в записи

формулы
слева направо).

Пример:
Составить таблицу истинности для функции
;

Выполняется
“по действиям”, как в 5м классе.

x₁	x₂
0	0	0	0	0
0	1	0	0	1
1	0	0	1	1
1	1	1	0	1

Приведение
функций к СДНФ и СКНФ.

Теория:

Полной
конъюнкцией
n
переменных называется конъюнкция,
состоящая из n
переменных или их отрицаний, в которых
каждая переменная встречается только
1 раз.

СДНФ
логической функции называется формула,
представляющая данную логическую
функцию и имеющая вид дизъюнкции полных
конъюнкций, которая формируется для
наборов переменных, для которых функция
f=1;

Полной
дизъюнкцией
n
переменных называется дизъюнкция,
состоящая из n
переменных или их отрицаний, в которых
каждая переменная встречается только
1 раз.

СКНФ
логической функции называется формула,
представляющая данную логическую
функцию и имеющая вид дизъюнкции полных
дизъюнкций, которая формируется для
наборов переменных, для которых функция
f=0;

Соседние файлы в папке Arkhiv_v_pomosch

Источник

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

Алгоритм построения таблицы истинности логической функции

Алгоритм построения логической функции по ее таблице истинности

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

Правила того, как следует проводить построение таблицы истинности

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

О порядке логических операций

Построения функции, если известна её таблица истинности

Логические выражения и таблица истинности

Пример 3. Построёте таблицу истинности для логического выражения

Вам также может понравиться

Как найти чему равен часть угла

Как найти мое местоположение на андроид

Как составить меню в детских садах

Добавить комментарий Отменить ответ