лаба 1 семестр 2

	МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «Белгородский Государственный Технологический Университет им. В.Г. Шухова» (БГТУ им. В.Г. Шухова) ИИТУС, Кафедра ТК
«Информационные технологии»
Лабораторная работа № 1.1 «Основы алгебра логики»
Выполнил: студент УС-11 Татаринов А.Е. Проверил: ст.преподават. Крюков А.В.		Отметка о выполнении дата, роспись	Отметка о защите дата, роспись

Вариант №9

Логика – это искусство приходить к

непредсказуемому выводу.

Сэмюэл Джонсон

Цель работы:

Изучение логических операций и правил их преобразований. Получение навыков практической работы по построению таблиц истинности, диаграмм Эйлера-Венна, синтезу логических выражений.

ЗАДАЧА 1

Постановка задачи: Задана булева функция от трех переменных:

А) При помощи логических функций табличного редактора (напр. MS Excel) или с использованием одной из сред программирования, постройте таблицу истинности (см. пример выполнения) для заданной булевой функции (такую таблицу истинности строить без каких-либо упрощений, пользуясь лишь встроенными логическими функциями И, ИЛИ, НЕ, ЕСЛИ).

Б) Упростить данное логическое выражение, содержащее только операции: отрицания, конъюнкции и дизъюнкции.

Решение

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

Определив порядок выполнения действий получаем расширенную таблицу.

В данном случае не все действия можно выполнить напрямую, потому как в MS Excel нет распознавания таких действий как следование, xor и т.д.

В этом случае большинство недоступных команд можно выполнить при помощи комбинирования команд ЕСЛИ и И.

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

Существует некоторая сложность с вводом таких операций как xor и следование, так как напрямую MS Excel не поддерживает их. Данную ситуацию можно исправить заменой этих операций на тождественно равные. Xor можно заменить операцией =ЕСЛИ (A<>B;1;0), а операцию следования можно записать в виде =ЕСЛИ (И(A=1;C=0);0;1).

Решим эту же задачу в среде программирования Pascal.

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

var

a, b, c: boolean;

begin

for a := false to true do

for b := false to true do

for c := false to true do

writeln(ord(a), ord(b), ord(c),

ord(not (not (a) xor b) and (not (a) or not (c))))

end.

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

Для упрощения данного выражения нам доступны такие операции как:

• Отрицания;

• Конъюнкции;

• Дизъюнкции.

Упростим исходное выражение

ЗАДАЧА 2

Постановка задачи: Выполнить задание. Ответ аргументировать, привести соответствующие фрагменты таких таблиц истинности.

Каждое из логических выражений A и B зависит от одного и того же набора из 6 переменных. В таблицах истинности обоих выражений в столбцах значений стоит ровно по 4 единицы в каждой таблице. Каково минимально возможное число единиц в столбце значений таблицы истинности выражения ?

Решение: так как выражения состоят из 6 переменных в каждом выражении по 64 строки. Каждое выражение содержит по 4 единицы в конечном столбце.

Выражение будет равняться единице только в том случае, если и В=1. в 60 строках, так как изначально А=1 в 4 строках: 64-4=60.

В=1 в 4 строках выражения. Отсюда можно сделать вывод, что может быть равное 1 не более чем в 4 строках таблицы истинности.

Рассмотрим данные рассуждения на наглядном примере. Построим возможные варианты таблиц истинности для данного выражения:

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

Так же возможны варианты, при которых совпадут 3, 2, 1 или 0 значений. Рассмотрим вариант, при котором не совпадет ни одного значения:

Ответ: 0.

ЗАДАЧА 3

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

Решение:

Рассмотрим первое выражение

Рассмотрим второе выражение

Рассмотрим последнее выражение

ЗАДАЧА 4

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

Решение

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

(A and B) or (A and C)

Для второго рисунка выражением будет:

(A or C) and not B

Для третьего рисунка

A and not B or A and C or A and B and C = A and not B or A and C

ЗАДАЧА 5

Постановка задачи: С помощью диаграмм Эйлера-Венна решить поставленную задачу:

Группа студентов в 36 человек сдавала экзаменационную сессию. Отличников в группе 5 человек. Число студентов, сдавших сессию только на «отлично» и «хорошо», равно числу студентов, сдавших сессию только на удовлетворительные оценки. 3 студента получили только хорошие оценки; 2 человека получили отличные, хорошие и удовлетворительные оценки; 11 человек получили только хорошие и удовлетворительные оценки. Удовлетворительные или хорошие оценки получили всего 28 человек. Студентов, получивших только отличные и удовлетворительные оценки, нет. Сколько студентов сдало сессию только на удовлетворительно? Сколько студентов получили отличные оценки? Сколько студентов не явились на экзамены?

Решение:

Составим модель задачи в форме диаграммы Эйлера-Вена.

B

E

A

C

D

F

G(не пришли)

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

A - получили только 5 B - получили только 4 C - получили и 4 и 5, но не 3 D - получили только 3 E - получили и 3 и 4, но не 5 F - получили и 3 и 4 и 5 G - не пришли

Составим систему уравнений и решим ее:

Подставив A = 5, B = 3, F = 2, E = 11 уравнения получим:

Подставив D = 8 + C во второе и третье уравнения получим

Ответ:

• Только на удовлетворительно сессию сдали D = 10 студентов;

• Отличные оценки получили A + C + F = 9 студентов ;

• Не явились на экзамены G = 3 студента.

ЗАДАЧА 6

Постановка задачи: По заданной таблице истинности (полной или неполной) составьте математическую запись соответствующей логической функции F (двумя способами).

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

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

2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.

3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.

4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент взять с отрицанием.

Следуя данному алгоритму построим нужное логическое выражение:

1. В данной таблице 3 строки с результатом 1, следовательно, в выражении будет 3 логических элемента.

2. Следуя 3-му и 4-му пункту запишем конечное выражение:

Рассмотрим второй способ.

1. Для этого отметим строки в которых функция принимает ложное значение:

2. Далее, анализируя данные составим подходящую функцию и упростим ее:

3. Далее инвертируем полученное выражение:

Ответ: .

ЗАДАЧА 7

Постановка задачи: Получить для данной формулы СДНФ и СКНФ (если это возможно) с помощью равносильных преобразований (без построения таблицы истинности).

Решение: для нахождения СДНФ проделаем следующие шаги:

1. Максимально упростим данное выражение:

2. Затем домножим к каждому члену выражения недостающие:

3. В результате получим СДНФ:

СКНФ функции будет иметь такой же вид как и упрощенное выражение:

Вывод: Следуя цели данной лабораторной работы, были закреплены теоретические и практические навыки по преобразованию логических операций. Получены навыки практической работы с таблицами истинности, диаграммами Эйлера-Венна.