I. Решение логических задач средствами алгебры логики

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

1. изучается условие задачи;

2. вводится система обозначений для логических высказываний;

3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

4. определяются значения истинности этой логической формулы;

5. из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Триггер — это электронная схема, широко применяемая в регистрах компьютера для надёжного запоминания одного разряда двоичного кода. Триггер имеет два устойчивых состояния, одно из которых соответствует двоичной единице, а другое — двоичному нулю.

Сумматор — это электронная логическая схема, выполняющая суммирование двоичных чисел.

Существует два основных класса компьютеров:

• цифровые компьютеры, обрабатывающие данные в виде числовых двоичных кодов;

• аналоговые компьютеры, обрабатывающие непрерывно меняющиеся физические величины (электрическое напряжение, время и т.д.), которые являются аналогами вычисляемых величин.

Информация всегда поступает от какого-либо объекта, который называют источником информации или источником сообщения.

Источники информации могут быть непрерывными или дискретными.

Дискретный источник в конечное время создает конечное количество информации. Дискретные сообщения слагаются из фиксированного набора отдельных элементов (знаков). Набор элементов конечен и называется алфавитом источника информации. С дискретными сообщениями работают цифровые ЭВМ.

Непрерывное сообщение создается непрерывным источником информации и представляется какой-либо физической величиной (электрическим напряжением, током и т.д.), изменения которой отображают протекание рассматриваемого процесса. Физическая величина, передающая непрерывное сообщение, может в определенном интервале принимать любые значения и изменяться в произвольные моменты времени. Поэтому непрерывное сообщение конечной длины, созданное непрерывным источником в конечное время содержит бесконечное количество информации. С непрерывными сообщениями работают аналоговые ЭВМ.

Литература:

1. Симонович С. Информатика. Учебный курс. - Санкт-Петербург: Питер, 2001 г.

Контрольные вопросы:

1. При составлении расписания на пятницу были высказаны пожелания, чтобы информатика была первым или вторым уроком, физика — первым или третьим, история — вторым или третьим. Можно ли удовлетворить одновременно все высказанные пожелания?

Приведите примеры истинных и ложных высказываний: а) из арифметики;   б) из физики; в) из биологии;   г) из информатики; д) из жизни.

Тема 2. Основы дискретной математики. Лекция № 4. Как решать логические задачи? (1час)

Кейс задания:

Задача на определение истинности составного высказывания.

 Истинность составного высказывания можно проверить либо построив таблицу истинности высказывания, либо упростив соответствующее логическое выражение по законам алгебры логики.

 ПОСТАНОВКА ЗАДАЧИ

Проверьте истинность следующего составного высказывания:

Х = “Высказывание “Неверно, что если Матроскин выиграл конкурс, то он получил приз” эквивалентна высказыванию “Матроскин выиграл конкурс, но приз не получил””

 РЕШЕНИЕ

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

А = “Матроскин выиграл конкурс”

В = “Матроскин получил приз”

S = “Неверно, что если Матроскин выиграл конкурс, то он получил приз”

R = “Матроскин выиграл конкурс, но приз не получил”

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

Ø - операция логического отрицания (инверсия);

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

Ú - операция логического сложения (дизъюнкция);

Þ - операция логического следования (импликация);

º - операция логического равенства (эквивалентности).

 Запишем соответствующие логические выражения:

S = Ø(А Þ В)

R = А Ù ØВ

X = S º R

Решение:

1 СПОСОБ

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

А Þ В = ØА Ú В

по закону де Моргана

Ø(АÚВ) = ØА Ù ØВ

Упростим выражение для высказывания S:

Ø(А Þ В) = Ø (ØА Ú В) = Ø(ØА) Ù (ØВ) = A Ù ØВ

Поскольку полученное выражение совпадает с выражением для высказывания R, мы можем утверждать, что высказывание Х истинное

Кейс-задание:

Истинность составного высказывания проверьте другим способом, построив таблицу истинности высказывания Х:

Задача на определение истинности составного высказывания (1час)

 

Истинность составного высказывания можно проверить либо построив таблицу истинности высказывания, либо упростив соответствующее логическое выражение по законам алгебры логики.