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

Операция НЕ - логическое отрицание (инверсия)

Операция ИЛИ - логическое сложение (дизъюнкция, объединение)

Операция И - логическое умножение (конъюнкция)

Операция «ЕСЛИ-ТО» - логическое следование (импликация)

Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)

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

Совершенная дизъюнктивная нормальная форма

Совершенная конъюнктивная нормальная форма

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

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

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

Правила ввода логической функции

Оставьте комментарий 6,950

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

Сортировка Основная Сначала простые Сначала сложные По популярности Сначала новые Сначала старые
Пройти тестирование по этим заданиям
Вернуться к каталогу заданий
Версия для печати и копирования в MS Word

Исполнитель А16 преобразует число, записанное на экране.

У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Умножить на 2

Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает его на 2.

Программа для исполнителя А16 – это последовательность команд.

Сколько существует таких программ, которые исходное число 3 преобразуют в число 12 и при этом траектория вычислений программы содержит число 10?

Траектория вычислений программы - это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.

Решение.

Искомое количество программ равно произведению количества программ, получающих из числа 3 число 10, на количество программ, получающих из числа 10 число 12.

Пусть R(n) - количество программ, которые число 3 преобразуют в число n, а P(n) - количество программ, которые число 10 преобразуют в число n.

Для всех n > 5 верны следующие соотношения:

1. Если n не делится на 2, то тогда R(n) = R(n - 1) + R(n - 2), так как существует два способа получения n - прибавлением единицы или прибавлением двойки. Аналогично P(n) = P(n - 1) + P(n - 2)

2. Если n делится на 2, тогда R(n) = R(n - 1) + R(n - 2) + R(n / 2). Аналогично P(n) = P(n - 1) + P(n - 2) + P(n / 2)

Последовательно вычислим значения R(n):

R(5) = R(4) + R(3) = 1 + 1 = 2

R(6) = R(5) + R(4) + R(3) = 2 + 1 + 1 = 4

R(7) = R(6) + R(5) = 4 + 2 = 6

R(8) = R(7) + R(6) + R(4) = 6 + 4 + 1 = 11

R(9) = R(8) + R(7) = 11 + 6 = 17

R(10) = R(9) + R(8) + R(5) = 17 + 11 + 2 = 30

Теперь вычислим значения P(n):

P(11) = P(10) = 1

P(12) = P(11) + P(10) = 2

Таким образом, количество программ, удовлетворяющих условию задачи, равно 30 · 2 = 60.

Ответ: 60.

Ответ: 60

Источник: Демонстрационная версия ЕГЭ-2017 по информатике.

1. Прибавить 1

2. Прибавить 3

Сколько существует программ, для которых при исходном числе 1 результатом является число 17 и при этом траектория вычислений содержит число 9? Траектория вычислений программы - это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 11, 12.

Решение.

Используем метод динамического программирования. заведем массив dp, где dp[i] - количество способов получить число i с помощью таких команд.

База динамики:

Формула перехода:

dp[i]=dp + dp

При этом не учитываются значения для чисел больше 9, которые можно получить из чисел меньше 9 (перескочив тем самым траекторию 9):

Ответ: 169.

Ответ: 169

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 29 ноября 2016 года Вариант ИН10203

Исполнитель Май17 преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 3

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3. Программа для исполнителя Май17 - это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 15 и при этом траектория вычислений содержит число 8? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 11, 12.

Решение.

Используем метод динамического программирования. Заведем массив dp, где dp[i] - количество способов получить число i с помощью таких команд.

База динамики:

Формула перехода:

dp[i]=dp + dp

Но при этом не учитываются такие числа, которые больше 8, но в них мы можем добраться из значения меньше 8. Далее будет приведены значения в ячейках dp от 1 до 15: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81.

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

Применяемое обозначение: А 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).
Все элементарные дизъюнкции различны.
Каждая элементарная дизъюнкция содержит переменную один раз.
Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.

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

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

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

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

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

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

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

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

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

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

Пример 6

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

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

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

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

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

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

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

Пример 7

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

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

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

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

X v Y & ¬ Z

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

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

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

Упражнение 8

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

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

2. F = X&¬ Yv Z.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 1.

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

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

Определяют количество столбцов: кол-во столбцов = кол-во переменных + кол-во логических операций. При определении количества логических операций учитывают также порядок их выполнения.

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

Рисунок 2.

Пример 1

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

Решение:

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

кол-во строк = $2^3 + 1=9$.

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

инверсия ($\bar{A}$);
дизъюнкция, т.к. она находится в скобках ($B \vee C$);
дизъюнкция ($\overline{A}\vee \left(B\vee C\right)$) – искомое логическое выражение.

Кол-во столбцов = $3 + 3=6$.

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

Рисунок 3.

Пример 2

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

Решение:

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

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

кол-во строк = $2^3 + 1=9$.

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

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

Количество логических операций и их последовательность:

отрицание ($\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}$).

Таблица истинности - это таблица, которая описывает логическую функцию. Логическая функция здесь - это функция, у которой значения переменных и значение самой функции выражают истинность. Например, они принимают значения «истина» либо «ложь» (true либо false, 1 либо 0).

Таблицы истинности применяются для определения значения какого-либо высказывания для всех возможных случаев значений истинности высказываний, которые его составляют. Количество всех существующих комбинаций в таблице находится по формуле N=2*n; где N - общее количество возможных комбинаций, n - число входных переменных. Таблицы истинности нередко используются в цифровой технике и булевой алгебре, чтобы описать работу логических схем.

Примеры : конъюнкция - 1&0=0, импликация - 1→0=0.

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

Инверсия; Конъюнкция; Дизъюнкция; Импликация; Эквиваленция; Штрих Шеффера; Стрелка Пирса.

Последовательность построения (составления) таблицы истинности:

Определить количество N используемых переменных в логическом выражении.
Вычислить количество всевозможных наборов значений переменных M = 2 N , равное количеству строк в таблице.
Подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество логических операций.
Озаглавить столбцы таблицы названиями переменных и названиями логических операций.
Заполнить столбцы логических переменных наборами значений, например, от 0000 до 1111 с шагом 0001 в случае для четырех переменных.
Заполнить таблицу истинности по столбцам со значениями промежуточных операций слева направо.
Заполнить окончательный столбец значений для функции F.

Таким образом, можно составить (построить) таблицу истинности самостоятельно.