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

Задачи

1. Составить таблицу истинности функции . Составить для нее СДНФ, построить карту Карно и упростить эту функцию и построить логическую схему для полученной после упрощения функции.

Решение.

Составим таблицу истинности на различных значениях переменных:

x	y

Запишем СДНФ.

Заполним карту Карно для этой функции:

 

Минимизация по карте Карно не дает упрощения, значит, это есть конечный результат.

Зарисуем логическую схему.

2. Дано выражение: . Упростить эту функцию на основе правил алгебры – логики и Булевой алгебры и построить логическую схему после упрощения функции.

Решение. Упростим функцию, используя свойства дистрибутивности, идемпотентности, поглощения, закон де Моргана, получим:

 

Карта Карно примет вид:

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

3. Дано выражение: . Упростить эту функцию и построить логическую схему для полученной после упрощения функции.

Решение. Упростим функцию, используя закон де Моргана, свойства дистрибутивности, идемпотентности, поглощения, получим:

Логическая схема соответствует схеме из примера 2.

4. Подобрать две функции, эквивалентные данной функции, но с меньшим числом операций и операндов: .

Решение.

5. Из указанных ниже функций отметить (с обоснованием) эквивалентные между собой функции:

o ;

o

o .

Указание: упростить и сравнить.

 

Решение.

 

 

6. Из указанных ниже функций отметьте (с обоснованием) эквивалентные между собой функции:

o ;

o ;

o ;

o ;

o .

Указание: упростить и сравнить.

Решение.

4. Информационно–логические задачи

 

1. Найти хотя бы один набор десятичных значащих цифр, соответствующий буквам: А, Б, В, Г при условии, что выполнено равенство

АБАВ + БАБ2 = ГГВ1.

Решение. Запишем условия решения задачи:

А+Б = Б + А = Г = 8.

В+2=11, В=9.

Г=8.

Одним из наборов чисел А и Б может быть выбран набор: А = Б = 4.

2. Найдите хотя бы один подходящий вариант наборов цифр для выполнения равенства вида:

ABCD + ECBF = A000C,

Решение. Так как А + Е должно равняться 10 вместе с перенесенной

единицей из младшего разряда, т.е. А + Е +1= 10, и, если учесть, что А равно 1, то Е = 8. Тогда можно записать:

А + Е + 1 = 10 à А= 1, Е = 8;

В + С +1 = 10

D + F = 10 + C.

Имеем 2 уравнения и три неизвестных. Одним из вариантов ответа может быть вариант: С =3, Д = 4, F = 9, B = 6.

Произведем проверку, получим:

АВСД + ЕСВF =

+ 8369

10003.

3. X, Y, Z, U, V должны поехать в разные города А, Б, В, Г, Д, Е. X может ехать только в А, Б, Д; Y может ехать только в А, Б и В; Z может ехать только в В; U не может ехать никуда, куда может ехать Y; V не может ехать только Д и Е. Необходимо определить, в каком городе мог быть каждый из них, если оказалось, что вдвоем они не были ни в одном городе. Указание: сделать таблицу возможностей поездок, строки которой пометить именами, а столбцы –городами.

Решение.

Путешественники	Города {A, Б, В, Г, Д, Е}	Результат
X	А	Б	Д	Д
Y	А	Б	В	А
Z	В			В
U=	Г	Д	Е	Г
V=				Б

 

 

4. Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. В ходе следствия Браун сказал, что преступники были на синем " Бьюике", Джонс сказал, что это был черный " Крайслер", Смит утверждал, что это был " Форд", но не синий. Каждый указал неправильно либо марку, либо цвет автомобиля. Определить истинный цвет и истинную марку автомобиля.

Решение.

Рассмотрим простые высказывания вида:

· х = " машина – синяя",

· у = " машина – Бьюик",

· z = " машина – черная",

· u = " машина – Крайслер",

· v = " машина – Форд".

На их основе высказывание Брауна можно записать в виде сложного логического выражения вида , высказывание Джонса – в виде , а высказывание Смита – в виде . Так как в каждом из этих выражений одна из переменных принимает значение " истина", то истинны и дизъюнкции вида: . По определению конъюнкции, . Это выражение мы взяли из-за однозначности равенства 1 конъюнкции и неоднозначности (много- вариантности) его равенства нулю. Упростим выражение:

Мы использовали тот факт, что одновременно не могут быть истинными два высказывания относительно цвета или два высказывания относительно марки машины. Так как конъюнкция истинна только тогда, когда , то заключаем, что автомобиль был черным " Бьюиком".

5. Студент А — отличник, у Б — пятерка или четверки, у В и Д — четверки или тройки, у Г — возможны все оценки. Какие оценки у каждого из них по контрольной работе, если все они получили различные оценки? Указание: студент А получил пятерку, следовательно, Б – четверку; продолжить далее рассуждения с учетом полученных раннее выводов.

Решение.

Введем логические переменные:

X – оценка за контрольную 5.

Y - оценка за контрольную 4.

Z - оценка за контрольную 3.

U - оценка за контрольную 2.

K - оценка за контрольную 1.

Введем функцию оценки знаний конкретного студента:

А: Х;

Б:

В:

Д:

Г:

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

Раскрытие скобок на основе законов Булевой алгебры дает ответ:

что противоречит утверждению, что каждый студент получил оценку отличную от оценок других студентов. Значит, чтобы решить задачу необходимо изменить условия задачи, например, пусть А может получить 5 или 2, и введем оценку 1, остальное оставим без изменений. Тогда ответ на поставленный вопрос будет иметь вид:

А получил 2; Б получил 5; В получил 4; Д получил 3; Г получил 1.

6. Андрей не может ехать в Малайзию и Китай. Николай хочет ехать только в Малайзию или Румынию. Геннадий не хочет ехать только в Уругвай. Сергей согласен ехать лишь в Румынию и Того, а Владимир может поехать в любую страну, кроме Китая, Уругвая и Того. Может ли каждый в одиночестве посетить одну из названных стран? Указание: сделать таблицу возможностей поездок, строки которой пометить именами, а столбцы – городами.

Решение.

	Малайзия	Китай	Румыния	Уругвай	Того	Результат
Андрей	+	+	_	_	_	Уругвай
Николай	+	_	+	_	_	Румыния
Геннадий				_		Китай
Сергей	_	_	+	_	+	Того
Владимир		_		_	_	Малайзия

Ответ: да.

7. Андрей и Петр — родственники Евгения, Дмитрий — родственник Николая и Петра. Кому должен приходиться родственником Николай, чтобы они все были родственниками друг другу? Указание: рассмотрите все возможные варианты для Николая.

Решение.

	Андрей	Петр	Евгений	Дмитрий	Николай
Андрей			+
Петр			+	+
Евгений	+	+
Дмитрий		+			+
Николай				+

Построим граф.

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

8. Имеются только вагоны вместимости 23 тонны и 37 тонн. Поезд из полностью загруженных вагонов с грузом в 883 тонны прибыл на станцию расцепления. Здесь из его вагонов сформировали и отправили поезд с 379 тоннами груза (без перегрузки и добавления других вагонов). Сколько вагонов каждой вместимости осталось в исходном поезде на станции расцепления? Ответ обосновать минимумом кратких и утвердительных рассуждений. Указание: необходимо решать соответствующие уравнения в целых числах, например, 23x+37y=883; начните с наименьшего возможного значения x (почему?).

Решение.

883т. - 379 т.= 504 т.

504 / 37 = 13 (вагонов по 37 т.) + 1 (вагон по 23 т.).

9. Обсуждая свои возможности по поступлению в вуз абитуриенты Андрей, Борис и Владимир высказали следующие предположения (в виде сложного высказывания, состоящего из двух простых высказываний) вида: Андрей — " Я не смогу поступить, а Владимир — поступит"; Борис — " Владимир не поступит, а Андрей — поступит"; Владимир — " Если я поступлю, то Борис — не поступит или наоборот". После сдачи экзаменов выяснилось, что каждый высказал одно верное и одно ложное простое утверждение. а) Кто поступил в вуз, если не смог поступить лишь один из них? б) Кто поступил в вуз, если поступил лишь один из них? Указание: выпишите логические выражения, соответствующие каждому высказыванию и упростите конъюнкцию, тождественно равную единице (истине).

Решение.

Введем в рассмотрение логические переменные:

x - поступит Андрей.

y - поступит Борис.

z – поступит Владимир.

Запишем логические рассуждения:

Андрей:

Борис:

Владимир:

Каждое из этих высказываний истинно в одном из событий, значит:

,

,

,

Логическое умножение этих функций даст ответ на вопросы:

Анализ полученного выражения показывает, что первое слагаемое отвечает на второй вопрос и ответ на него такой: не поступит Андрей и не поступит Владимир, а поступит Борис. Второе слагаемое говорит о том, что поступит Владимир и поступит Андрей, а Борис не поступит, т.е. отвечает на первый вопрос.