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

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

Алгебра логики (алгебра высказываний) — это формальная логическая теория, раздел математической логики, разработанный в XIX в. в трудах английского математика Джорджа Буля. В алгебре логики используются Алгебраические ме­тоды для решения логических задач.

Объектами алгебры логики являются Высказывания.

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

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

В булевой алгебре (алгебре логики) возможны только два значения для логических высказываний и логических констант:

• ИСТИНА — обозначается как True или 1;

• ЛОЖЬ — обозначается как False или 0.

Примеры высказываний: «сегодня теплое утро», «^5 — иррациональное число».

Не являются высказываниями следующие предложения:

• «пойдет ли сегодня дождь?» — вопросительное предложение, не имеющее своим значением ИСТИНА или ЛОЖЬ;

• «сделайте домашнее задание» — повелительное предложение; невозможно определить значение высказывания — истинно оно или ложно;

• «это предложение ложно» — противоречивое утверждение.

Законы алгебры логики помогают определить истинность или ложность составных высказываний, не вникая в их содержание. Поэтому простым выска­зываниям ставятся в соответствие логические переменные. Например: А — для высказывания «Андрей Иванов — врач», В — «Андрей Иванов — шахматист», Xj— «этот карандаш красного цвета», X2~«этот карандаш синего цвета».

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

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

В алгебре логики существуют три основные операции.

1. Логическое отрицание (инверсия).

Обозначается: A, —A, Not А, не А.

Высказывание —А истинно при ложном А и ложно при истинном Л.

2. Логическое умножение (конъюнкция).

Обозначается А&В, A And В, АЛ, А л В, АВ, А и В.

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

3. Логическое сложение (дизъюнкция).

Обозначается: A v В, A Or В, А + В, А или В.

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

Остальные операции алгебры логики выражаются через первые три опе­рации — отрицание, конъюнкцию и дизъюнкцию. Перечислим их.

4. Логическое следование (импликация).

Обозначается: A → В, А о В.

Высказывание A → В ложно только тогда, когда А истинно, а В ложно.

Важно: В операции импликации посылка А не обязана быть истинной, в отличие от логического оператора в языках программирования «если А То В».

Импликация выражается через дизъюнкцию и отрицание:

А =>В = — AvB.

5. Эквивалентность (равносильность, необходимость и достаточность).

Обозначается: A ~ В, A <=>В, A ≡ В.

Высказывание AoBИстинно тогда и только тогда, когда значения А иВ Совпадают.

Эквивалентность выражается через отрицание, дизъюнкцию и конъюнкцию:

AoB = (-A V В) л (^B V А).

6. Исключающее ИЛИ.

Обозначается: A XORВ, А®В

Высказывание A XOR В истинно, когда А и В не равны.

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

Составное высказывание (логическая формула) Состоит из нескольких высказываний, соединенных логическими операциями. Исходные высказывания
могут быть логическими переменными или логическими константами (имеющи­ми постоянное значение ИСТИНА или ЛОЖЬ).

Логическая функция Определяется на множестве логических перемен­ных и логических констант, принимающих значение ИСТИНА или ЛОЖЬ. Значение функции вычисляется в результате выполнения логических операций с (или над) логическими операндами. Например,

F (А, В, С) =A л (—IВ V С); F(Xj, ×τ X3) = ->Xj v X2Л —∣ X3.

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

Таблицы истинности простейших логических функций:

Законы алгебры логики

Закон	Для ИЛИ	Для И
Коммутативный (переместительный): Логические переменные можно менять местами	XvY =YvX	XaY=YaX
Ассоциативный (сочетательный): Логические переменные в дизъюнкциях и конъюнкциях можно объединять в группы	(Xv Y)vZ = Xv(Yv Z)	(XaY)AZ = Xa(YaZ)
Дистрибутивный (распределительный): Одинаковые переменные в дизъюнкциях и конъюнкциях можно выносить за скобки	(Jv У) A Z = = (XaZ)V (YaZ)	(XaY)VZ = = (XvZ)A(YvZ)

Окончание таблицы

Закон	Для ИЛИ	Для И
Закон непротиворечия: Высказывание может быть только истинным или ложным, третьего не дано		Xκ^X=0
Закон исключенного третьего: Высказывание может быть только истинным или ложным, третьего не дано	%v-lλr= 1
Правила де Моргана	-1(Arv У) = -XЛ—«У	-1(%λ Y) = — Xv->Y
Законы склеивания	(Хл У) V (—I Arл У) = У	(Xv Y)λ(-XvУ) = У
Исключение констант	ArvO = A,, Xv 1 = 1	Λγλ0 = 0, Хл1 =X
Двойного отрицания: Двойное отрицание исключает отрицание	^-X = X
Идемпотентности	XvX = X	XkX = X
Контрапозиции	A → В = ^B → —А
Снятие импликации	X→ y=-∣Xv У
Снятие эквивалентности	А <->В = (А л В)V (-1А л -15) A <->В = (A V -1В) л (-1А V В)
Закон поглощения	АV (А л С) = A	А л (А V С) = А

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

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

1 —ι (х А —I х) V (у V —у)= —10 V 1 = 1.

Правило де Моргана Ассоциативный закон Операция переменной с ее инверсией Операция с константами

4(х V У) л(-X V У) А (—X V —У) =

Повторяется второй множитель — разрешено зако­ном идемпотентности

= (χ∖∕Y)^(—х V у) л (—х v у) л (—х v — у) =

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

= У ^ -^∙

5 —∣(x л УV —∣z) = Снимаем знак отрицания, чтобы он стоял перед

Отдельными переменными, а не перед их комбина­циями — правило де Моргана

=—∣(x л У) А —I—∣z = Правило де Моргана и закон двойного отрицания

= (—X V —У) л Z.

6 XAφyVXΛJ, AZVXΛZΛ∕7=XΛ(yA(l VZ)VZΛ∕?) = = XA(yVZAjp) = XAyVXAZA/?.

Выносятся за скобки общие множители, применяется правило операций с константами

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

Таблица истинности логической формулы (функции) выражает соответствие между всеми возможными наборами значений логических переменных и зна­чением функции.

Для функции от двух переменных существует 22= 4 комбинации наборов значений переменных; для функции трех переменных — 23= 8; для функции че­тырех переменных — 24= 16 комбинаций значений наборов переменных.

В общем случае для функции от NПеременных количество строк MВ та­блице истинности вычисляется по формуле:

M=In.

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

1) определить количество NИспользуемых переменных в логическом выражении;

2) вычислить количество всевозможных наборов значений переменных M= 2N,Равное количеству строк в таблице истинности;

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

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

5) заполнить столбцы логических переменных наборами значений, например, от 0000 до 1111 с шагом 0001 в случае для четырех переменных;

6) заполнить таблицу истинности по столбцам со значениями промежуточных операций слева направо;

7) заполнить окончательный столбец значений для функции F.

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

Функция с двумя переменными: F(X,Y) = — хлуV -∣(х v У)V Х.

Пере­менные	Промежуточные логические формулы	Функция F
X	У	—∣X	Лу	XV У	-1 (XVy)	—ιXΛy V-I (х V у)	—∣X А у V—i (Х V у) V X
0	0	1	0	0	1	1	1
0	1	1	1	1	0	1	1
1	0	0	0	1	0	0	1
1	1	0	0	1	0	0	1

Функция с тремя переменными: F = —∣(х v —У)V —∣x л Z.

Переменные	П	Ромежуточные логические формулы	Функция F
X	У	Z	—у	XV-ιy	-1(xv-1y)	—IX	-IXAZ	—ι(xv-ty) V — IXAZ
0	0	0	1	1	0	1	0	0
0	0	1	1	1	0	1	1	1
0	1	0	0	0	1	1	0	1
0	1	1	0	0	1	1	1	1
1	0	0	1	1	0	0	0	0
1	0	1	1	1	0	0	0	0
1	1	0	0	1	0	0	0	0
1	1	1	0	1	0	0	0	0

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

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

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

(А л —В А С)V (—А л В) \/ (—В А —0.

Любое логическое выражение можно привести к ДНФ.

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

(А а —В л 0 v (—А л В л 0 V (А л —В л -10.

Правила построения логической функции по таблице истинности лучше всего разобрать на примере.

1 Пусть задана полная таблица истинности некоторой функции:

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

1. Из таблицы надо удалить строки, в которых значение функции равно 0:

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

2. Для каждой строки, в которой значение функции равно 1, составляется конъюнкция из всех переменных. Переменная входит в конъюнкцию со знаком отрицания, если эта переменная в этой строке равна 0:

X	У	Z	F	Вспомогательный столбец
0	1	0	1	—IX Ay A -1Z
1	0	0	1	XА —У A ~~∣Z
1	0	1	1	XЛ —у Л Z
1	1	1	1	X Лу AZ

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

F(Xiу, Z) = (—∣X лул~τZ) V (хA -у Л —∣Z) v (х л —∣y л z) v (х л у л z).

Разбор типовых задач ЕГЭ

1Демо-вариант 2009 г., задача А 7)

Для какого из указанных значений XИстинно высказывание √(^>2)→(Λ>3))?

1) 1 2)2 3)3 4)4

Решение. К решению данного типа задач следует приступать «с конца». Последняя операция в выражении — отрицание к импликации. Построим таблицу истинности для операции отрицания импли­кации:

А	В	A→B	^{A→B)
0	0	1	0
0	1	1	0
1	0	0	1
1	1	1	0

В задаче ставится вопрос об истинности высказывания, т. е. нас интересует значение «1» в последнем столбце таблицы:

А	В	-ΛA→B)
1	0	1

Вместо А и В вставляем выражения из исходной формулы:

Х>2	А>3	-√(X>2)→(X>3))
1	0	1

Выражение X> 2 должно принимать значение «истина», т. е. Λr>2.

Выражение X > 3 должно принимать значение «ложь», т. е.

Ar<=3.

Решая систему неравенств, получаем, что X= 3

Ответ: 3.

2 (Демо-вариант 2009 г., задача А9)

Символом FОбозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.Дан фрагмент таблицы истинности выраже­ния F:

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

↑)^Xλ^Yλ^Z 2)XλYλZ 3)XvYvZ 4)-^Yv-1Tv^Z

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

Для данной задачи процесс решения можно сделать более ко­ротким, если заметить, что:

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

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

Тем самым мы быстро отбросили два варианта, а для оставших­ся двух придется делать вычисления для всех наборов данных, представленных в таблице.

Ответ: 4.

3(Демо-вариант 2007 г., задача AlO)

Какое логическое выражение равносильно выражению -∣(А А В) л -,С?

L)-AvBv-,C 2) (-A v-∣B) л—∣C

3) (-Av-∣B)λC 4) —А л ^BЛ

Решение. Данную задачу можно решить двумя способами.

Способ !.Логические преобразования

К выражению —∣(А л В) применяем правило де Моргана:

-л (А л В) = (—A v->5).

В результате получим (—Av—∣B) л —∣C,Что соответствует ответу №2.

Способ 2. Табличный

Для функции —I (ЛлВ) л —∣C надо построить таблицу истин­ности. Это логическое выражение содержит три логические переменные, поэтому всего будет восемь наборов значений переменных, для которых нужно вычислить значение функции. Построение такой таблицы лучше производить поэтапно. По правилу приоритета логических операций сначала выполняется действие в скобках (т. е. конъюнкция ЯаВ), а затем к ней стро­ится отрицание. На следующем шаге необходимо построить от­рицание третьей логической переменной C(чему соответству­ет шестой столбец таблицы). Значение исходного выражения —I (ЛлВ) л —>С вычисляется как конъюнкция двух последних по­лучившихся столбцов.

А	В	C	А лВ	-I (А л В)	C	-I (А л В) л
0	0	0	0	1	1	1
0	0	1	0	1	0	0
0	1	0	0	1	1	1
0	1	1	0	1	0	0
1	0	0	0	1	1	1
1	0	1	0	1	0	0
1	1	0	1	0	1	0
1	1	1	1	0	0	0

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

Ответ: 2.

4 Какое из приведенных имен удовлетворяет условию:

(Первая буква согласная) v (Вторая буква гласная)—>(В слове 4 буквы) 1) МИХАИЛ 2) ГРИГОРИЙ 3) ЕВГЕНИЙ 4) ИОЛАНТА?

Решение. Введем обозначения для высказываний:

• первая буква согласная — Л;

• вторая буква гласная — 5;

• в слове 4 буквы — К.

Тогда исходное высказывание примет вид (A v В) → К. Преобразуем его: -,(A v В)V К = (~ιA л ~ιB) v К.

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

А	В	-л	-в	-Лл-В	К	(-Л л-В) V К
0	0	1	1	1	0	1
0	1	1	0	0	0	0
1	0	0	1	0	0	0
1	1	0	0	0	0	0

Логическая функция принимает значение ИСТИНА только на одном наборе входных данных: первая буква — гласная, вторая — согласная и в слове не 4 буквы. Из предложенных вариантов ответов подходит только третий.

Ответ: 3.

5Какое из приведенных имен удовлетворяет условию:

(Вторая буква гласная → Первая буква гласная) л Последняя буква согласная

1) АЛИНА 2) МАРК 3) ДАРЬЯ 4) АЛЕКСАНДР?

Решение. Введем обозначения для высказываний:

• вторая буква гласная — А,

• первая буква гласная — В,

• последняя буква согласная — P

Тогда исходное высказывание примет вид (A →B) л Р.

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

Л	В	Л→B	P	(A→B) л P
0	0	1	1	1
0	1	1	1	1
1	0	0	1	0
1	1	1	1	1

Логическая функция принимает значение ИСТИНА на трех на­борах входных данных:

1) первая, вторая и последняя буквы — согласные (ответ №4);

2) первая буква — гласная, вторая — согласная, последняя — согласная (таких вариантов нет);

3) первая и вторая буквы — гласные, последняя — согласная (та­ких вариантов нет).

Из предложенных вариантов ответа подходит только четвертый.

Ответ: 4.

6 Каково наименьшее натуральное число X, при котором истинно высказы­вание

(AT∙ Af<8O)→((Ar+ 1) ∙ (X+ l)>80) ?

Решение. Раскроем импликацию, получим = (X[1][2][3]< 80) v ((Ar+l)2> 80).

Избавимся от отрицания: (X2 ≥ 80) v ((ATl)2> 80).

Это выражение истинно, когда истинно либо X2 ~≥ 80, либо (ATI)2> 80. Рассмотрим оба этих случая.

1. Так как речь идет о натуральных (т. е. положительных) чис­лах, X2>8£> истинно при X >4л/5. Округлив, получаем X > 9^

2. (ATI)2> 80 истинно при X+ 1 > 4√5 т. е X> 4√5 — 1. Окру­глив, получим Ar≥ 8.

Сопоставив этих два результата, получаем X ≥ 8.

3. Это логическое выражение будет ложным, когда ложны оба выражения в скобках. Тогда можно записать систему уравне­ний:

J 4vJI∕vM=0, (1)

I К л — M=O. (2)

4. Из (1) получаем: — L=O, M=O, АН), значит! = 1, M= 0,N = 0.

5. Подставим M=O в (2), получим: К л 1 = 0. Значит, К= 0.

6. Запишем значения переменных К, L, MnNВ указанном по­рядке: 0100.

Ответ: 0100.

8 Сколько различных решений имеет уравнение

((Jл —J) v —AT v L) a M= 1,

Где J, К, L, M—Логические переменные? В ответе не нужно перечислять все различные наборы значений J, К, L, М, при которых выполнено дан­ное равенство. В качестве ответа нужно указать количество таких набо­ров.

Решение. Надо решить уравнение (^K v М) →(-L v Mv N)=Q.

1. Упростим исходное выражение. По закону непротиво­речия Ja — J=O. Запомним, что J может принимать любое значение. Получаем: (0 v ~,K v L) л M = 1, что равносильно (-LTvL) a M = 1.

2. Полученное выражение истинно, когда истинны оба члена конъюнкции: M = 1 и — LT v L = 1.

Нетрудно видеть, что полученная система двух уравнений име­ет три различных решения, но при этом J — любое.

Ответ: 6.

9 Сколько различных решений имеет уравнение

(

Где J, К,L, M — логические переменные? В ответе не нужно перечислять все различные наборы значений J, К,L, М, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение. 1. Преобразуем выражение и вынесем —MЗа скобку, используя дистрибутивный закон:

-Λ√v ((-К V — Z) л (Z v — W)) = О-

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

∫ — M = 0, (1)

I ((-Wv-Z)λ(Zv-W>) = 0. (2)

3. Из (1) следует, что M=I.

4. Выражение (2) будет ложным, если ложно хотя бы одно вы­ражение в скобках. Перепишем (2) как систему двух уравне­ний:

Г — Wv-Z = O, (3)

I Zv-W=O. (4)

5. (3): — W v-Z = 0, тогда K= 1 и Ш = 1, a N—Любое (2 реше­ния).

6. (4): Z V — W = 0, тогда Z = OhW = 1, а К — любое (еще 2 реше­ния).

Общее количество решений равно сумме количеств решений каждого уравнения, то есть 4.

Ответ: 4.

10 Сколько различных решений имеет система уравнений

W7 v-W2 = 1, (1)

X2 V — WJ=I, (2)

X9 V—XlO = 1. (9)

Решение. Можно решать эту систему следующим образом.

Способ 1.

1. Предположим, что у нас есть только одно уравнение (1). Это импликация. Данное уравнение имеет 3 решения.

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

3. Для трех уравнений получим 5 решений.

4. Для 9 уравнений (10 переменных) будет 11 решений.

Способ 2.

1. Пусть Xl = 0, тогда из (1) Х2= 0, из (2) ХЗ= 0, из (9) XlO = 0. Получаем первый набор:

Xl	Х2	ХЗ	Х4	Х5	Х6	Х7	Х8	Х9	XlO
0	0	0	0	0	0	0	0	0	0

2. Пусть Xl = 1, тогда если Х2= 0, то из (2) ХЗ= 0, из (9) XlO = VhПолучаем второй набор:

Xl	Х2	ХЗ	Х4	Х5	Х6	Х7	Х8	Х9	XlO
1	0	0	0	0	0	0	0	0	0

3. Если Х2= 1, тогда из (3), если ХЗ = 0, то из (4) Х4= 0, …, из (9) XlO = VkПолучаем третий набор:

Xl	Х2	ХЗ	Х4	Х5	Х6	Х7	Х8	Х9	XlO
1	1	0	0	0	0	0	0	0	0

И т. д.

Если занести все решения в таблицу, то получим:

Xl	Х2	ХЗ	Х4	Х5	Х6	Х7	Х8	Х9	XlO
0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0
1	1	0	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0	0
1	1	1	1	0	0	0	0	0	0
1	1	1	1	1	0	0	0	0	0
1	1	1	1	1	1	0	0	0	0
1	1	1	1	1	1	1	0	0	0
1	1	1	1	1	1	1	1	0	0
1	1	1	1	1	1	1	1	1	0
1	1	1	1	1	1	1	1	1	1

Ответ: 11.

Задачи к разделу «Алгебра логики»

В задачах 1-6 символом FОбозначено одно из указанных в задаче логиче­ских выражений от трех аргументов: X,Y, Z∙

Дан фрагмент таблицы истинности выражения F.Какое выражение соот­ветствует F?

у л 3)(xaу) v(—∣y л —∣z) 4)aΓΛ-ιzvz » width=»172″ height=»95″ class=»»/>

1) Yv(X→Z)

2) Ya(XvX)

3)-X→(XaZ)

4)(YvZ)aX

2)Z→(YvX)

3) (XaY)ЛZ 4)(X→->Y)aZ

X	Y	Z	F	L)(Xv У) aZ
0	0	1	0	2)Z→ Y
1	0	1	0	3) CYaУ) a-,Z
1	0	1	0	4)(X→ У) л Z
1	1	1	1

7 Укажите, для какого из указанных значений XИстинно высказывание √√X>15)→(X>16))

А) 15 Б) 16 В) 17 Г) 18

8 Укажите, для какого из указанных значений XИстинно высказывание (Х>10)→(50>(X + 1)).

А) 40 Б) 51

В) 52 Г) 50

9 Для какого из указанных значений XИстинно высказывание (JY*(AT8) >-25+2*X) → (Х>7) ?

1) 4 2) 5

3) 6 4) 7

10 Для какого из указанных значений XИстинно высказывание

(X*(X-16)> -64) ->	► (Х>8) ?
1) 5 2) 6	3) 7 4) 8

11Для какого из указанных значений XЛожно высказывание (X>7) → (X- нечетное) ?

1) 9 2) 8

3) 7 4) 6

12 Для какого из указанных значений XЛожно высказывание (X — нечетное) → (А>7) ?

1) 9 2) 8

3) 7 4) 6

13 Для каких из указанных значений Хи YИстинно высказывание: (Y>X) л (Y+X>0) л (У<1)?

1) Х=0, У=0 3) Х=0, У=1

2) Х=0, У= 1/2 4) X= 1/2, У= 1/2

14 Для каких из указанных значений Хи YИстинно высказывание: (Y<X)Л (У+Х<0) л (Г>-1)?

1) Х=0, У=0 3) X=0, Y=-I

2) Х=0, У=-1/2 4) X= 1/2, У—1/2

15 Для какого из указанных значений XЛожно высказывание: (Х<15) л (Х>12) → (Х<14)?

16 Каково наибольшее целое число X, при котором ложно высказывание ((X-12)∙X+36 > 0) → ((X+1)∙(X-1) > 39)?

17 Каково наибольшее целое число X, при котором ложно высказывание ((X-10)∙X+25>0) → (X∙X>30)?

18 Каково наибольшее целое число X, при котором истинно высказывание (X∙(X+1) > 99) → (X∙X< 80)?

Каково наибольшее целое число X, при котором истинно высказывание (X∙(X+1) > 60) → (X∙X< 50)?

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

Каково наибольшее целое число X, при котором истинно высказывание (50(X+l)∙(X+l))?

В задачах 22 — 48 преобразуйте логические выражения.

22 (А л -В) V (—А л В) л (Л V В) 23 ->(AvB)λ —∣(A л -1(ВV — U))

24 (—А л В) V (А л В л (A V — В)) 25 -1 (—A V В) л (А л -1(ВV -∏Λ))

26 (А л В) V (—A V В) A (A v -15)

27 —I (√4 V —ιβ) а —1 (—U а —1 (-BvA)) 28 (АV —В) л (—А л ВV А л В) 29 -1(А л В) л ->(A V -1 (-BvA)) 30 (АV В) л ((А л — В) V (-A л В))

31-п(Л A^B)A—I(A v (^g л Л)) 32 (^Л л -В) V ((-А A-В)V (Л л В)) 33 (А л В) л —∣(А л-> (BaA)) 34 (А а—В) V V -,(В V А)) 35 (—А V В) л (—А А В) л (—АV —В) 36 -1(А л —В) л -, (А л В) а (А а — В) 37 (А л — В) V(^Л л В) V (А а В) 38 —। (—А V В) V—। (Л V —। (—В а —(Л)) 39 —L(А а В A -∣Q л (-A V —∣(В A -∣Q) 40 —I (—А а —В л Q л (Л V — I (-B A—∣C)) 41 (A V ВV -1Q A — I (A V — I (В A Q) 42 —∣(AvBvC)V—∣ (—A V —I (В а —∣Q) 43 (A A -I (В л —∣Q) л -1(Л V V Q) 44-п(Л λB)λ-1(Cλ^)λ-1(5λ-∣Q)

^45~~∣-1(Л V 5) V-η (С V-J) V-1 (-u5 V Q)

46-I (А V В V -,Q V — I (->(A a -^B) V С)

47^∣Xa YaZ v-Xa YaZ

48∏(Xa-X) V Yа (Ха Yv Y)

49 Укажите, какое логическое выражение равносильно выражению -(-Л А — В) V — С.

∖)AaBa^C 2)AvBvC

3)~'(AaB)→^C 4) Л VB V —C

50 Укажите, какое логическое выражение равносильно выражению (-Я л — В) V — C

1) (-A V — Q a (-B V — Q 2)AvBvC

3)AaBv-C 4)-Л a-Cv-В a-C

51 Укажите, какое логическое выражение равносильно выражению (А V — В) л-А.

1) (А V — В) л А 2) -А А -В

3) -АV — В 4) (-A Л В) л-А

52 Укажите, какое логическое выражение равносильно выражению -(-A V — В) A—CaD.

V) А а В A—CaD 2) Av—BaCaD

3) —A V Bv —C A D А)-А а — В л C A D

53Укажите, какое логическое выражение равносильно выражению —А V А а В.

1)B 2)-В 3)-AvB 4)-А л В

54 Укажите, какое логическое выражение равносильно выражению — А л ВV А.

1)B 2)-В 3) A V В 4) А а В 55 Укажите, какое логическое выражение равносильно выражению

-(А А-В) А С.

∖)-AvBaC 2) (-A V В) л C

3)-Av Ba—C 4) -А л В л C 56 Укажите, какое логическое выражение равносильно выражению

-(-А А — В) V — С.

↑)AaBv—C 2)AvBvC

3) -А А -В V C 4)AvBv—C

В задачах 57 — 63 по известной таблице истинности запишите логическую функцию и преобразуйте ее.

57

А	В	C	F
О О О о 1 1 1 1	О о 1 1 о о 1 1	О 1 о 1 о 1 о 1	О 1 о о о 1 о 1

58

А	В	C	F
О о о о 1 1 1 1	О о 1 1 о о 1 1	О 1 о 1 о 1 о 1	1 1 1 о 1 о о о

59

А	В	C	F
О о о о 1 1 1 1	О о 1 1 о о 1 1	О 1 о 1 о 1 о 1	1 о 1 о о 1 о 1

60

А	В	C	F
О о о о 1 1 1 1	О о 1 1 о о 1 1	О 1 о 1 о 1 о 1	1 1 о о о о 1 1

61

А	В	C	F
О о о о 1 1 1 1	О о 1 1 о о 1 1	О 1 о 1 о 1 о 1	О 1 о 1 1 о 1 о

62

А	В	C	F
О о о о 1 1 1 1	О о 1 1 о о 1 1	О 1 о 1 о 1 о 1	1 1 о 1 о 1 о о

63

А	В	C	F
О о о о 1 1 1 1	О о 1 1 о о 1 1	О 1 о 1 о 1 о 1	О 1 1 о 1 1 о о

В задачах 64 — 66 по заданному логическому выражению постройте таблицу истинности.

64 (BaQv (~В Л ~,C) 65 (А л -,B) V (-\4 л Q v (~В л Q

66 (~NA л В л ~,Q λ(AλBλC)λ(Aλ~В л-i0

В задачах 67 — 74 выберите правильный ответ.

67Для какого слова ИСТИННО высказывание

(1 буква — гласная) a-, (3 буква — согласная) v (4 буква — гласная)?

L)abcde 2)bceda 3) abedc 4)bcade 68Для какого символьного набора ЛОЖНО высказывание:

(Первая буква — гласная) → ((Вторая буква — согласная) л (последняя буква — согласная))

1) Арбалет 2) Пробка 3)Кран 4) Арка

69Для какого символьного набора ЛОЖНО высказывание:

((Первая буква — гласная) а -{Вторая буква — гласная)) → (Третья буква — согласная)

L)Kpoτ 2) Атака 3) Арбуз 4) Оазис

70Какое из приведенных имен удовлетворяет логическому условию: (первая буква согласная → вторая буква согласная) л последняя буква гласная

1)EΓOP 2) АЛЕНА 3) СТАНИСЛАВ 4) ТАТЬЯНА?

71Для какого из названий животных ЛОЖНО высказывание:

Третья буква гласная → Заканчивается на гласную букву л В слове 7 букв?

1) Леопард 2) Страус 3) Кенгуру 4) Верблюд 72Для какого из названий животных ЛОЖНО высказывание:

Третья буква гласная → Заканчивается на гласную букву v В слове 6 букв?

1) Пума 2) Леопард 3) Кенгуру 4) Страус

73Какое из приведенных имен удовлетворяет логическому условию: — (последняя буква гласная → первая буква согласная) л вторая буква согласная

1) ИРИНА 2) АРТЕМ 3) СТЕПАН 4) МАРИЯ?

74Какое из приведенных имен удовлетворяет логическому условию — (первая буква гласная → вторая буква гласная) л последняя буква гласная

1) ИРИНА 2) МАКСИМ 3)APTEM 4) МАРИЯ?

В задачах 75 — 80 необходимо найти значения логических переменных Ki LiMmNiУдовлетворяющих указанному логическому уравнению. Ответ запишите в виде строки из четырех символов — значений переменных Ki Li Mm N(в указанном порядке). Так, например, строка 1001 соответствует тому, что K=Ii L=Qi M=Qi N=I.

75(K→-M)V(-LλMλK)V~N=Q

7B~](-(MvZ)λK)→(-∕Ca-M)vj∕V) = 0

77~∣(-(-MvK) λN)λ(M→L) = 1

78~](K→M)V (Nv —L) V— (-M л L) = 0

79~∣-К v Ka-Z a-Mv Ka Z л-Mv Ka Z a M= 0 80 (KvM)→(Mv-ZvΛ) = 0

В задачах 81 — 99 определите количество решений логического уравнения с четырьмя логическими переменными. В ответе не нужно перечислять все различные наборы значений, при которых выполнено данное равен­ство. В качестве ответа нужно указать КОЛИЧЕСТВО таких наборов.

81 ((KvL) →(LλMλN)) = Q

Jλ—KλLλ — Ma (Nv —N) = Q

-МлКл —Nλ—Jλ(Lv —L) = 0

((А V —А) л —В A C A D) V —В= 0

(K→LλM)λ(-NvN)=Q

86 (Мл — М) V (K→ — N) у(N→L)=0 87((A → В) л С) V (D л — D) = О

8¾Γ∣((A → В) л Q V (DЛ — D) = 1

89^(M→ К) л (-M → —N)A-(L→M)=∖

9θ] (M→K)a(-M→L)a(K→L) = 1 91 АV 5 V -Cv(Da-D) = 1 92 (А л -A) V В V — C V (DЛ -D) = 1 93(K→J)a(MaNaL)v(Ka-J)a-(MaNaL)=∖

94∏(N → (М A K)) a(-M→ L) λ(K→ L) a(M→К)=1

95~∣(M→ L)a(L→K)a(L→-М) A(K→M)a(O→N)=∖

96∏((J→K)→(MaNaL))a((Ja-K)→-(MaNaL))a(M→ J) = 1

97~∣((-N→P)→(Kλ La M)) л(-(-N Л -P) → (-Kv — L v -M))= 1 98 ((KaLaM)→(-N→P))a((-Kv-Lv-M)→(NvP))= 1