Практическая работа №2

«Решение задач и упражнений по образцу: построение таблиц истинности сложных высказываний с использованием законов построения сложных высказываний»

Цель работы: изучить различные законы построения сложных высказываний, научиться строить таблицы истинности сложных высказываний.

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

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

Требуемое время: 2 часа

Предварительное домашнее задание: Калмыкова Е.А. Информатика: Учеб. Пособие для студ.сред. проф. образования. / Е.А. Калмыкова, И.А. Кумскова. – М.: Издательский центр «Академия», 2005. – стр. 50 – 58.

Пояснения к работе.

Логика- наука, изучающая методы установления истинности или ложности одних высказываний на основе истинности или ложности других высказываний.

Основы логики заложил в 4 веке до н.э. древнегреческий ученый Аристотель.

Правила вывода истинности высказываний, описанные Аристотелем, (силлогизмы ) оставались основным инструментом логики вплоть до второй половины XIX в, когда в трудах Дж. Булля, О де Моргана и др. возникла математическая логика, которая все прежние достижения логики перевела на точный язык математики.

Логика относится к числу дисциплин, образующих математический фундамент информатики.

Основой внутреннего языка Компьютера является язык логики, булева алгебра.

Основные понятия математической логики.

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

Например:

“Лёд- твёрдое состояние воды” - истинное высказывание.

“Треугольник- это геометрическая фигура” - истинное высказывание.

“Париж- столица Китая” - ложное высказывание.

B<5- ложное высказывание.

Логические величины: понятия, выраженные словами: ИСТИНА, ЛОЖЬ (TRUE , FOLSE)

Следовательно, истинность высказывания выражается через величины.

Логические константы- ИСТИНА ИЛИ ЛОЖЬ.

Логическая переменная: символически обозначенная логическая величена.

Следовательно, если известно, что A,B,X,Y и пр.- переменные логические, то это значит, что огни могут принимать значение только ИСТИНА ИЛИ ЛОЖЬ.

Логическое выражение- простые или сложные высказывания.

Сложные строятся из простых, с помощью логических операций(связок).

Л огические операции. В математической логике определены пять основных логических операций: конъюнкция 1-ые три

дизъюнкция составляют

отрицание полную систему

импликация операций

эквивалентность

В информатике обычно используют первые три операции.

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

Конъюнкция (логическое умножение)

В русском языке выражается союзом “и”.

В математической логике используются знаки & или .

Конъюнкция - двухместная операция, записывается в виде

Р=AB или Р= A&B.

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

Таблица истинности функции логического умножения

X	Y	Р=X*Y
0	0	0
0	1	0
1	0	0
1	1	1

Дизъюнкция (логическое сложение)

В русском языке этой связке соответствует союз ИЛИ.

В математической логике оно обозначается знаком V .

Дизъюнкция- двухместная операция, записывается в виде

Р = A v B

Значение этого выражения будет ИСТИНА , если значение хотя бы одного из операторов истина.

Таблица истинности функции логического сложения

X	Y	Р=X+Y
0	0	0
0	1	1
1	0	1
1	1	1

Отрицание.

В русском языке этой связке соответствует союз НЕ .

Отрицание- одноместная (унарная операция)

В математической логике оно обозначается знаком  А или А.

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

Таблица истинности функции логического отрицания

Х	Р = Х
0	1
1	0

Импликация (логическое следование, от implicatio – тесно связывать)

Эта операций в классической логике выражается словосочетанием “Если.., то .” или В необходимо для А , А достаточно для В.

Импликация - двухместная операция, записывается в виде

Р=А→В.

По определению импликация всегда истинна , за исключением случая когда А истинно ,а В ложно.

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

А	В	Р=А→В
0	0	1
0	1	1
1	0	0
1	1	1

Из первых двух строчек таблицы следует , обычно использующееся в классической логике, утверждение “из лжи можно вывести всё что угодно” , то есть получить как истинное, так и ложное высказывание. Например А) Если 2+3=4, то 2*2=4 Б) Если 2+3=4, то 2*2=5

Очень часто высказывание, стоящее после слова “Если” , называется основанием или посылкой ,а стоящее после слова “то” называется следствием или заключением. Например “Если идет дождь, то земля мокрая”.

Здесь простое высказывание “идет дождь” – основное , а следствие “земля мокрая”.

Эквиваленция (эквивалентность, дойная импликация, от aequivalens – равноценное, равнозначное).

Операция равенства, выражаемое связками «тогда и только тогда», «необходимо и достаточно», «…равносильно…», называется эквиваленцией или двойной импликацией.

Эквиваленция двухместная операция, обозначается

Р=А↔В или

Р=АВ.

Сложное высказывание Р=А↔В (читается: А эквивалентно В) истинно тогда и только тогда, когда А истинно и В истинно, либо А ложно и В ложно, т.е. когда совпадают. В остальных случаях Р=А↔В ложно.

Таблица истинности составного высказывания А↔В .

А	В	Р=А↔В
0	0	1
0	1	0
1	1	0
1	1	1

Порядок выполнения логических операций:

1. Операция отрицания (НЕ)

2. Операция конъюнкции (И)

3. Операция дизъюнкции (ИЛИ)

4. Операция импликации.

Основные законы алгебры логики.

Переместительный закон коммутативности:

Для логического сложения

xy=yx

x+y=y+x

для логического умножения

xy=yx

xy=yx

Сочетательный закон ассоциативности:

Для логического сложения

x(yz)=(xy)z

x+(y+z)=(x+y)+z

для логического умножения

(x/\y)/\z=x/\(y/\z)

(xy)z=x(yz)

Распределительный , или дистрибутивный, закон:

Для логического сложения

(x\/y)/\z=(x/\z)\/(y/\z)

(x+y)z=xz+yz

для логического умножения

(x/\y)\/z=(x\/z)/\(y\/z)

xy+z=(x+z)(y+z)

Закон инверсии:

Для логического сложения

x\/y = x /\ y

x +y=xy

для логического умножения

x/\y = x \/ y

x y = x + y

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

Всегда истинные высказывания:

X+1=1

X + x= 1(закон исключённого третьего)

Всегда ложные высказывания

X*0=0

X &Х=0(закон противоречия)

Значения аргумента и функции.
1	2	3	4	5	6	7	8	9	10
x	y	x	y	х+y	х+y	xy	x y	x y	X +y
0	0	1	1	0	1	0	1	1	1
1	0	0	1	1	0	0	1	0	1
0	1	1	0	1	0	0	1	0	1
1	1	0	0	1	0	1	0	0	0

Обобщение всегда истинных и всегда ложных высказываний приводит к следующим выводам, пригодным для любых логических формул(обозначим их буквой Р)

Р\/1=1; P*0=0

P\/P=1; p* p =0

К аксиомам алгебры логики относятся следующие соотношения

ХХ=Х; Х+Х=Х;

1*X=X; X ¯ XY=0

XXX…X=X; X(X+Y)=X

Х+XY=X; X+X+…+X=X

Х+XY+XZ =X.

Задания для самостоятельной подготовки

Изучить:

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

• Основные законы алгебры логики

• Порядок выполнения логических операций