http://217.19.221.117/informatika/reshenie-zadanij-iz-testov-3.html

Глава 3: Основы логики.

базисные элементы изображены согласно ГОСТ 2.743-91

Дизъюнкция	Конъюнкция	Сложение по mod 2	Эквивалентность
Импликация	Коимпликация	Элемент Вебба	Элемент Шеффера

- в языке Basic операции AND - конъюнкция, EQV - эквивалентность, IMP - импликация, NOT - отрицание, OR - дизъюнкция, XOR - сложение по mod 2 выполняются поразрядно;

- в языке Pascal операция div означает частное, а операция mod - остаток от деления первого операнда на второй операнд, функция Odd принимает истинное значение при нечетном аргументе, функция Length возвращает длину строки, функция Copy(X,J,L) возвращает подстроку длины L строки X, начиная с J-того символа.

Часть а.

Решение заданий из тестов

 

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

а)   отрицание (инверсия) обозначается "¬"  (например, ¬ А или );

б)   конъюнкция (логическое умножение, логическое И) обозначается " "  или & (например, А  В, А&В);

в)   дизъюнкция (логическое сложение, логическое ИЛИ) обозначается " " (например, A  В);

г)   следование (импликация) обозначается " " (например, А   В);

д)   равносильность, эквивалентность обозначается “≡” или “↔” (например, А ≡ В или А ↔ В);

е)   символ "1" используется для обозначения истины (истинного высказывания), символ "0" — для обозначения лжи (ложного высказывания).

 

2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А В и (¬ A) В равносильны, a A В и А   В — нет (значения выражений разные, например, при А = 1, В = 0).

3. Приоритеты логических операций: отрицание, конъюнкция, дизъюнкция, следование.  Таким образом, ¬А B С D совпадает с ((¬А) В) (C D). Возможна запись А B С вместо (А  В) С. То же относится и к дизъюнкции:  возможна запись    A В C вместо  (A В) C.

 

 

 

2004-—А11. Для какого имени истинно высказывание:

¬ (Первая буква имени гласная)   (Четвертая буква имени согласная) ?

1) ЕЛЕНА;      2) ВАДИМ;     3) АНТОН;     4) ФЕДОР.

Решение. Поскольку истинным должно быть отрицание импликации, то это возможно только в одном случае: если из истины следует ложь, отрицание которой — истина. Этому условию отвечает только имя под № 3.

Ответ: 3.

 

 

 

 

2004—А12. Какое логическое выражение равносильно выражению ¬ (A ¬B) ?

1) A В;         2) А В;         3) ¬А ¬B;     4) ¬А В.

Решение. Есть два способа решения.

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

Из расположенной ниже таблицы замечаем, что правильный ответ — № 4.

 

А	В	¬(A ¬B)	A В	А В	¬A ¬B	¬А В
истина	истина	ложь	истина	истина	ложь	ложь
истина	ложь	ложь	истина	ложь	истина	ложь
ложь	истина	истина	истина	ложь	истина	истина
ложь	ложь	ложь	ложь	ложь	истина	ложь

 

Второй способ — равносильное преобразование выражения (в нашем случае это применение законов де Моргана и двойного отрицания): ¬(A ¬B) ≡¬A В. Приходим к тому же результату.

Ответ:  4.

 

 

 

 

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

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

 

X	У	Z	F
0	0	0	1
0	0	1	0
0	1	0	1

 

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

1) ¬Х ¬Y Z;           2) ¬X ¬Y Z;      3) X Y ¬Z;             4) X У Z.

            Решение. Возможный вариант решения — переборный и выбор нужного результата.

Ответ:  3.

 

 

 

 

2004—В2. Укажите значения переменных К, L, М, N, при которых логическое выражение (¬К M) (¬L M N) ложно. Ответ запишите в виде строки из четырех символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К = 1, L = 1, M = 0, N = 1.

            Решение. Составим таблицу истинности

 

К	L	M	N	¬K M	¬L M N	(¬K M)→( ¬L M N)
1	1	1	1	1	1	1
1	1	1	0	1	1	1
1	1	0	1	0	1	1
1	1	0	0	0	0	1
1	0	1	1	1	1	1
1	0	1	0	1	1	1
1	0	0	1	0	1	1
1	0	0	0	0	1	1
0	1	1	1	1	1	1
0	1	1	0	1	1	1
0	1	0	1	1	1	1
0	1	0	0	1	0	0
0	0	1	1	1	1	1
0	0	1	0	1	1	1
0	0	0	1	1	1	1
0	0	0	0	1	1	1

 

Ответ: 0100.

 

 

 

2005—А9. Для какого числа X истинно высказывание

Х> 1   ((Х< 5) → (Х< 3)):

1) 1;                2) 2;                3) 3;                4) 4.

Ответ  2.

 

 

 

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

 

 

Решение. Возможный вариант решения — переборный и выбор нужного результата.

Ответ: 4.

 

 

 

 

2*.  Выбрать условие, проверяющее принадлежность точки с координатами (X,Y) заштрихованной области

 

 

Решение. Возможный вариант решения — переборный и выбор нужного результата.

Ответ: 5.

 

 

 

 

3*. Структурная формула для переключательной схемы

 

 

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

раскрывая скобки и используя законы логики (переменные, к которым применены законы логики, выделены), получаем

 Ответ: 1.

 

 

4*. Комбинационная схема устройства

 

 

реализует логическую функцию F равную

Решение. Согласно правилам, выражаем базисные элементы, затем упрощаем полученное выражения, используя правила логики:

 Ответ: 3.

 

2004-А2. Выражение

(9X²+4Y²>36) или не (((X+Y)²≥4) или (X²>│X+Y│))

истинно при следующих значениях набора переменных:

1) X=0, Y=3; 2) X=-1, Y=0; 3) X=0, Y=-2; 4) X=1, Y=1; 5) X=0, Y=0.

Решение.

Пусть (9X²+4Y²>36)=A, (X+Y)²≥4=B , X²>│X+Y│=C.

1. X=0, Y=3, тогда А=0; В=1; С=0; В или С =1, не (В или С)=0 – выражение ложно;

2. Х=-1, Y=0, тогда А=0; В=0, С=0; В или С =0, не (В или С)=1 – выражение истинно;

3. Х=0, Y=-2, тогда А=0; В=1, С=0; В или С =1, не (В или С)=0 – выражение ложно;

4. Х=1, Y=1, тогда А=0; В=1, С=0; В или С =1, не (В или С)=0 – выражение ложно;

5. Х=0, Y=0, тогда А=0; В=0, С=0; В или С =0, не (В или С)=1 – выражение истинно.

Ответ: 2, 5.

 

 

 

2006-А3 Множество точек выделенной на рисунке области равно

 

 

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

Результат совпадает с выделенной областью условия задачи, следовательно, вариант 1 является решением.

Аналогично рассматриваем все варианты:

 

Результат не совпадает с областью, данной в условии задачи, следовательно вариант 2) не удовлетворяет условию задачи.

 

Результат не совпадает с областью, данной в условии задачи, следовательно вариант 3) не удовлетворяет условию задачи.

 

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

 

 Результат совпадает с выделенной областью условия задачи, следовательно, вариант 5 является решением.

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

Ответ: 1, 4, 5.

 

 

 

 

 

2006-А4. Структурная формула для переключательной схемы

имеет вид

Решение: По переключательной схеме записываем логическую формулу:

Примечание: +-дизъюнкция, *- конъюнкция, ^--отрицание

 

 

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

Наборы совпали – правильный ответ 1 (остальные варианты можно не проверять, т.к. по условию ответ один).

Ответ: 1.

 

 

 

 

 

2004-А4. Структурная формула для переключательной схемы:

имеет вид:

Решение: способ 1). По переключательной схеме записываем логическую формулу:

Составляем таблицы истинности для формулы и для каждого из ответов

Наборы не совпали, следовательно, вариант 1) не удовлетворяет.

 

Наборы не совпали, следовательно, вариант 2) не удовлетворяет.

 

Наборы не совпали, следовательно, вариант 3) не удовлетворяет.

 

Наборы не совпали, следовательно, вариант 4) не удовлетворяет.

 

Наборы  совпали, следовательно, вариант 5) является решением.

 

Способ 2) Строим по схеме логическое выражение и упрощаем его:

 

Ответ: 5.

 

 

 

 

 

2006-А5. Комбинационная схема устройства

 

реализует логическую функцию F равную

1) 1                 2) А                 3) В                 4) 0                 5)

Решение:

Способ 1) Строим логическую функцию по комбинационной схеме устройства:

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

Значение логической функции F совпадает со значением

Ответ: 5.

 

Способ 2) Рассмотрим возможные наборы, которые могут принимать значения А и В, подставим каждую пару в схему и проанализируем полученное значение функции F:

А	В
0	0
0	1
1	0
1	1

1) А=0, В=0, на схеме после обозначения каждой операции отмечено значение, приобретаемое каждым элементом для выбранных значений А и В:

Получаем значение функции F=1.

 

2) А=0, В=1

\

Получаем значение функции F=0.

 

3) А=1, В=0

Получаем значение функции F=1.

 

4) А=1, В=1

Получаем значение функции F=0.

По результатам можно построить следующую таблицу для значений А и В и значений функции F, получающихся при каждом наборе:

 

А	В	F
0	0	1
0	1	0
1	0	1
1	1	0

 Получаем значение функции F совпадающее со значением

Ответ: 5.

 

 

 

 

2005-А6. Условие изменения значения логической функции

при одновременном изменении аргументов А и В равно :

Решение: строим таблицу истинности для выражения

 

 

Одновременное изменение аргументов А и В происходит в наборах 001 и 111, которые соответствуют строкам 2 и 8 таблицы. То есть переключение схемы будет происходить при переходе с первого набора на второй или, выражая через логические операции, получим формулу:

, строим для нее таблицу истинности

 

Далее строим таблицы истинности для вариантов ответов задания, и сопоставляем наборы с набором для формулы .

 

Наборы не совпали, следовательно, вариант 1 – не является решением.

 

Наборы совпали, следовательно, вариант 2 – решение. (остальные можно не проверять, т.к. по условию задание имеет одно решение)

Ответ: 2.

 

 

 

 

2006-А7 Тождественно истинными (тавтологиями) являются логические формулы

Решение: Составляем таблицы истинности для каждой формулы.

Не является тавтологией.

 

 Где Z= А→В, X= В→С, Y= А→С, W= X→Y

Является тавтологией

 

Не является тавтологией

 

 Является тавтологией

Ответ: 1, 4.

 

 

 

 

 

2006-А8 Корень Х = F( A,B) логического уравнения

равен

 

Решение:

1) Подставляем значения в логическое уравнение. Если значения левой и правой части равенства совпадут, значит, данное значение Х является корнем уравнения. Обозначим  W=A+B

 

Правая часть равенства

Части не совпали, значит  вариант 1) не является корнем уравнения

 2). Подставляем значения Х= А→В в логическое уравнение. Если значения левой и правой части равенства совпадут, значит, данное значение Х является корнем уравнения. Обозначим

Обе части равенства совпали, значит вариант 2) – корень уравнения.

Ответ: 2.

 

 

 

 

 

2005-А8. Корень X = F(A, B) логического уравнения

 равен

 Покажем примеры решения для вариантов корней:

1) Подставляем в левую и правую части уравнения вариант 1), т.е. Х= А→В

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

Наборы в правой и левой частях уравнения не совпали, следовательно, вариант 2 не является корнем уравнения.

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

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

 Наборы в правой и левой частях уравнения не совпали, следовательно, вариант 5 не является корнем уравнения.(можно не проверять )

Ответ: 4

 

 

 

 

 

2005-А9. Специализированный компьютер выполняет поразрядные операции над сумматором и регистрами от A до Z. Машинный язык компьютера содержит следующие команды: 

Команда	Означает
A?	Ввод данных в регистр А
A!	Вывод данных из регистра А
A	Переслать данные из сумматора в регистр А
*A	Сохранить без изменения единичные разряды сумматора, соответствующие нулевым разрядам регистра А, остальные разряды сумматора инвертировать.

 Функция F(A,B), вычисляемая программой  A?B?F*F*FF*FR*R*A*F*B*FFF!  равна

 Решение: Запишем в регистры А и В такие двоичные значения, чтобы поразрядно оказались всевозможные комбинации 0 и 1. 

Команда	Значение в регистре	Значение в сумматоре
А?	0011
В?	0101	1000
F	1000	1000
*F		0111
*F		1111
F	1111	1111
*F		0000
R	0000	0000
*R		1111
*A		1100
*F		0011
*B		1110
*F		0001
F	0001
F!	0001

0011

0101

0001           Это соответствует АВ.

Ответ: 1

 

 

 

 

 

2006-А9. Специализированный компьютер выполняет поразрядные операции над сумматором и регистрами от A до Z. Машинный язык компьютера содержит следующие команды: 

Команда	Означает
A?	Ввод данных в регистр А
A!	Вывод данных из регистра А
A	Переслать данные из сумматора в регистр А
А*В	Сохранить без изменения единичные регистра А, соответствующие нулевым разрядам регистра В, остальные разряды регистра А инвертировать.

 Функция F(A,B), вычисляемая программой  A?B?F*АА*АF*АF*BB*BA*BF*AF!  равна

 Решение: Решение задач данного типа может быть следующим:

1) Поскольку, конечные ответы не зависят от конкретных значений А, B, F, будем рассматривать значения регистров A, B, F в формуле

 F*A A*A F*A F*B B*B A*B F*A  равными А = 1010, В = 1011, F = 1111. Причем, выполнение операции F*A,  влечет за собой изменение значения регистра F.

2) Выполним последовательно все операции в функции:

1.F*A  2.A*A  3.F*A  4.F*B  5.B*B  6.A*B  7.F*A

 

3) F [1110]  Таким образом, при выполнении команды F! из регистра F выведется 1110.

Выполним логические операции, предложенные в ответах со значениями А=1010, В=1011 поразрядно.

 1110 – совпадает с полученным нами ответом, следовательно, функция F(A,B) вычисляемая программой в задании, равна A≡B.

Ответ: 2.

 

 

 

 

 

 

2004-А10.Три подразделения A,B и C торговой фирмы стремились получить по итогам года прибыль. Экономисты высказали следующие предположения:

- либо подразделения А и B получат прибыль одновременно, либо одновременно не получат;

 - получение прибыли подразделением С равносильно тому, что получение прибыли подразделением В не будет достаточным основанием для получения прибыли подразделением А;

- ни подразделение А и ни подразделение С не получат прибыль.

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

1) А,С                         2) А,В,С          3) А,В            4) В,С             5) А

Решение. Обозначим А высказывание «подразделение А получит прибыль», В – «подразделение В получит прибыль», С – «подразделение С получит прибыль». Тогда,

• высказывание «либо подразделения А и В получат прибыль одновременно, либо одновременно не получать» запишем А↔В

• высказывание «получение прибыли подразделением С равносильно тому, что получение прибыли подразделением В не будет достаточным основанием для получения прибыли подразделением А» запишем

• высказывание «ни подразделением А и ни подразделением С не получит прибыль» запишем   

Построим таблицу истинности для этих трех формул:

 Случай, когда из трех предложений два истинно, реализуется на единственном наборе значений А=1, В=1, С=0

Ответ: 3.

 

 

 

 

 

2005-А10. Три подразделения А, В С торговой фирмы стремились получить по итогам года прибыль. Экономисты высказали следующие предположения:

 - подразделение А получит прибыль только тогда, когда получение прибыли подразделением С не будет достаточным основанием для получения прибыли подразделением В;

- подразделения А и С не получат прибыль;

- подразделение А или подразделение С получит прибыль.

По завершению года оказалось, что только одно из трех предположений истинно.

Это означает, что прибыль получили

1) А, С                        2) А, В, С        3) А, В                        4) В, С            5) А

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

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

 В результате получаем только одну единицу в строке 8, чему соответствуют единицы для переменных А, В и С, то есть прибыль получили подразделения А, В и С.

Ответ: 2.

 

 

 

 

 

2006-А10. Три подразделения А, В С торговой фирмы стремились получить по итогам года прибыль. Экономисты высказали следующие предположения:

- получение прибыли подразделением В равносильно тому, что получит прибыль подразделение А или получит прибыль подразделение С;

- неверно, что подразделение В получит прибыль или получат прибыль подразделение А и подразделение С;

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

По завершению года оказалось, что только одно из трех предположений ложно.

Это означает, что прибыль получили

1) А, С                        2) А, В, С        3) А, В                        4) В, С            5) А

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

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

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

Ответ: 3.

 

 

 

 

 

2006-А15. Структурная формула для логической схемы имеет вид

Решение:  По логической схеме составляем формулу, начиная с конца:

 Ответ: 2.

 

 

 

 

 

2006-А16. Из приведенных логических схем эквивалентными являются схемы с выходными сигналами

 1) F2 и F3;                  2) F3 и F4;                  3) F1 и F3;

4) F1 и F4;                  5) F2 и F4                   6) нет эквивалентных схем

Решение:  Строим  по логическим схемам формулы, затем проверяем по таблице истинности, для каких наборов А и В совпали значения формул:

 Наборы совпали для F1 и F3, следовательно, схемы, соответствующие этим выходным сигналам эквивалентные.

Ответ: 3.

 

 

 

 

 

2006-А16. На входе логической схемы

 при F=1 невозможна следующая комбинация сигналов (А,В,С)

1) (0;0;1)                     2) (0;1;0)                     3) (0; 1; 1) 

4) (1;0;0)                     5) (0;0;0)                     6) нет верного ответа

Решение:  Подставляем каждую из комбинаций в схему, получаем при А=0, В=1, С=1 F =0.

Ответ: 3.

 

 

 

 

 

2004-В8. Оператор алгоритмического языка BASIC

PRINT(15 OR 51)EQV NOT(51IMP(15 XOR 85))

выведет число, равное___.

Решение: PRINT(15 OR 51)EQV NOT(51IMP(15 XOR 85))

                                                1          5      4         3            2

Обозначили порядок выполнения поразрядных действий и перевели числа 15, 51 и 85 в двоичную систему счисления:

А=15=1111, В=51= 110011, С=85=1010101

 Результаты выполнения действий :

1) А OR В = 00111111

2) А XOR С = 01011010

3) В IMP 2) = 11011110

4) NOT 3) = 00100001

5) 1) EQV 4) + 11100001, т.к. старший разряд =1 , то число отрицательное.

Обратный код   00011110

                               +      1

                               11111  = -31

Ответ: -31

 

 

 

 

 

2006-В8. Оператор алгоритмического языка BASIC

  PRINT (51 OR 85) XOR (85 IMP NOT (15 EQV 51))  

выведет число, равное ____

Решение:

51 = 00110011;   85 = 01010101;    15 = 00001111

51 OR 85 =(00110011 OR 01010101) = 01110111

 15 EQV 51= 00001111 EQV 00110011=11000011

NOT (15 EQV 51) = 00111100

85 IMP NOT (15 EQV 51) = 01010101 → 00111100 = 10111110

XOR – сложение по модулю 2.

(51 OR 85) XOR (85 IMP NOT (15 EQV 51))  = 01110111 XOR 10111110 =11001001

т.к. старший разряд =1 , то число отрицательное.

Обратный код   00110110

                               +      1

                               110111₂=-55₁₀

Ответ: -55

 

 

 

 

 

2004-В20. База данных «Преподаватели», наряду с другими, имеет поля с названиями «кафедра» и «должность». В базе данных находятся записи о профессорах, доцентах и ассистентах кафедр физики и химии. Количество записей N, удовлетворяющих различным запросам, приведено в следующей таблице

 Количество записей, удовлетворяющих запросу «должность≠профессор или кафедра=химия», равно_____.

Решение. Введем обозначение доцх (доцент кафедры химии), ассх (ассистент кафедры химии), профх (профессор кафедры химии), доцф (доцент кафедры физики), ассф (ассистент кафедры физики), профф (профессор кафедры физики).

Количество записей, удовлетворяющих запросу «кафедра=химия и должность=доцент», равно 11, значит

доцх=11.

Количество записей, удовлетворяющих запросу «должность=доцент или должность=ассистент», равно 29. Значит,

доцх +доцф+ассх+ ассф=29; доцф+ассх+ ассф=29-11=18.

Количество записей, удовлетворяющих запросу «неверно, что (должность=ассистент или кафедра=физика)», равно 18. Это означает

доцх+профх=18.

Запрос «должность≠профессор или кафедра=химия» равносилен выражению  доцх +профх+ассх +ассф+доцф=18+18=36.

Ответ: 36.

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

1. Операция логического отрицания (инверсия) А: “Сегодня в 12 часов дня я был на катке.” В: “Сегодня я был на катке не 12 часов дня.” С: “Я был на катке в 12 часов не сегодня.” D: “Сегодня в 12 часов дня я был в кино.” E: “Сегодня я был на катке в 3 часа дня.” F: “Сегодня в 12 часов дня я не был на катке.” Рассмотрим высказывания A и F. Высказывание F истинно, если А - ложно и наоборот. Его называют отрицанием высказывания А. Присоединение частицы “не” к сказуемому данного простого высказывания А называется логическим отрицанием. Указание о выполнении операции логического отрицания над высказыванием обозначается с помощью черточки над буквой. - указание выполнить логическое отрицание над высказыванием А. Иногда используют другое определение: присоединение слов “неверно что...” ко всему данному высказыванию есть логическое отрицание. Пример: А: “5 является делителем числа 30” : “Число 5 не является делителем числа 30.”

Логическая операция ИНВЕРСИЯ

• соответствует частице НЕ;

• обозначается черточкой над именем переменной;

• иначе называется ОТРИЦАНИЕ.

Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна. Таблица истинности инверсии имеет вид:

A
0	1
1	0