Математика и информатика (стр. 5 )

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

Пример 4

Являются ли следующие формулы тавтологиями?

а) Х\/Х; б) (Х/\Y)® (X\/Y).

Решение.

Для ответа на этот вопрос нужно составить таблицы истинности этих формул.

а) Х\/Х

X	X	Х\/Х
1	0	1
0	1	1

Формула принимает значение Истина при любых значениях переменной X, следовательно, это тавтология:

б) (Х/\Y)->(X\/Y).

Х	Y	X	(Х/\Y)	(X\/Y)	(Х/\Y)® (X\/Y)
1	1	0	1	1	1
1	0	0	0	1	1
0	1	1	0	1	1
0	0	1	0	0	1

Формула в последнем столбце имеет значение Истина при всех значениях входящих в неё переменных. Это также тавтология.

Раздел 7. Равносильность формул

логики высказываний

Предложения являются равносильными, если они одновременно истинны либо ложны при одних и тех же значениях переменных. Например:

а) х=2 и 2х=4;

б) "Завтра будет дождь" и "Неверно, что завтра не будет дождя".

Если пример а) достаточно очевиден, то для примера б) рассмотрим доказательство.

Пусть X – это элементарное высказывание "Завтра будет дождь", тогда X обозначает высказывание "Завтра не будет дождя".

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

Рассмотрим таблицу истинности этих формул:

X	X	X
истина	ложь	истина
ложь	истина	ложь

Сравнивая столбцы 1 и 3, можно убедиться, что они имеют одинаковые значения истинности. Следовательно, они равносильны.

Формулы F1 и F2 называются равносильными, если их эквиваленция F1 « F2 тавтология.

Напомним, что эквиваленция истинна тогда и только тогда, когда составляющие ее высказывания оба истинны либо оба ложны. Следовательно, F1 и F2 есть тавтология в том и только в том случае, если формулы F1 и F2 «одновременно», т. е. при одинаковых наборах значений переменных, входящих в формулы, принимают одинаковые значения.

Говорят, что предложения Р1 и Р2 равносильны в логике высказываний, если соответствующие им формулы равносильны.

Равносильность двух формул логики высказываний (а также соответствующих этим формулам предложений) обозначается символом º. Запись F1º F2 означает, что формула F1 равносильна формуле F2.

Свойства отношения равносильности

Отношение равносильности обладает следующими свойствами:

а) рефлексивности: Fº F;

б) симметричности: если F1º F2, то F2º F1;

в) транзитивности: если. F1º F2 и F2º F3, то F1º F3.

Законы логики высказываний

Равносильности формул логики высказываний часто называют законами логики. Перечислим наиболее важные из них:

1.  X º X – закон тождества.

2.  X/\Xº л – закон противоречия.

3.  X\/Xº и – закон исключенного третьего.

4.  X º X – закон двойного отрицания.

5.  X/\Xº X; X\/Xº X – законы идемпотентности.

6.  X/\YºY/\X; X\/YºY\/X – законы коммутативности (переместительности).

7.  (X/\Y)/\ZºX/\(Y/\Z); (X\/Y)\/ZºX\/(Y\/Z) – законы ассоциативности (сочетательности).

8.  Х/\(Y\/Z)º(X/\Y)\/(X/\Z); Х\/(Y/\Z)º(Х\/Y)/\(Х\/Z) – законы дистрибутивности (распределительности).

9.  X/\Y º X\/Y; Х\/Y º Х/\Y – законы де Моргана.

10.  Х/\иº Х; Х\/лº Х.

11.  Х/\лº л; Х\/иº и.

12.  Х/\(Х\/Y)º Х; Х\/(Х/\Y)º Х – законы поглощения.

13.  (Х\/Y)/\(Х\/Y)º Y; (Х/\Y)\/(Х/\Y)º Y – законы склеивания.

Равносильные преобразования

Если какую-нибудь формулу F1, являющуюся частью формулы F заменить формулой F2, равносильной F1, то полученная формула окажется равносильной F.

На этом основании имеем:

X\/X/\YºX\/X/\Y (по закону двойного отрицания);

X\/X/\YºX\/(X\/Y) (по закону де Моргана);

Х\/(Х\/Y)ºХ\/(Х\/Y) (по закону двойного отрицания);

Х\/(Х\/Y)º(Х\/Х)\/Y (по закону ассоциативности);

(Х\/Х)\/YºХ\/Y (по закону идемпотентности).

Замену формулы другой, ей равносильной, будем называть равносильным преобразованием данной формулы.

Под упрощением формулы, не содержащей знаков ® и «, условимся понимать равносильное преобразование, приводящее к формуле, которая не содержит отрицаний неэлементарных формул (в частности, двойных отрицаний) или содержит в совокупности меньшее число знаков /\ и \/, чем исходная.

Задачи для самостоятельного решения

Примечание: подчеркивание внизу означает логическое отрицание.

В задачах 1-25 в соответствии с законами алгебры логики составьте таблицы истинности для следующих формул:

1.  XÙY

2.  YÙX

3.  XÚY

4.  XÚY

5.  X®Y

6.  X®Y

7.  XÚY®XÙY

8.  Х/\Y

9.  X\/Y

10.  X®Y

11.  (X\/Y) ® Y

12.  X«Y

13.  X«Y

14.  X\/X®Y

15.  X\/(X\/Z)

16.  (X/\Y)/\Z

17.  X « (Y/\Z)

18.  (X/\Y)\/Z

19.  (X\/Y) « Z

20.  X\/(Y\/Z)

21.  Х/\(Y\/Z)

22.  (X/\Y)\/(X/\Z)

23.  Х® (Y/\Z)

24.  (Х\/Y)/\(Х\/Z)

25.  Z®X/\Y

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

26.  (Х/\Y) ® (X\/Y) X/\Y

27.  XÚY XÚY

28.  XÙY (XÚY)®Y

29.  XÙY XÙY

30.  XÚY XÚY

31.  XÚY XÙY

32.  XÚY XÙY

33.  XÙY XÚY

34.  XÙY XÚY

35.  X/\Y X\/Y

36.  Х\/Y Х/\Y

37.  X\/X/\Y X\/X/\Y

38.  X\/X/\Y X\/(X\/Y)

39.  Х\/(Х\/Y) Х\/(Х\/Y)

40.  Х\/(Х\/Y) (Х\/Х)\/Y

41.  (Х\/Х)\/Y Х\/Y

42.  Х/\(Х\/Y) Х

43.  Х\/(Х/\Y) Х

44.  (Х\/Y)/\(Х\/Y) Y

45.  (Х/\Y)\/(Х/\Y) Y

46.  (X/\Y)/\Z X/\(Y/\Z)

47.  (X\/Y)\/Z X\/(Y\/Z)

48.  Х/\(Y\/Z) (X/\Y)\/(X/\Z)

49.  Х\/(Y/\Z) (Х\/Y)/\(Х\/Z)

50.  (X/\Y) « (Z®X) (X/\Y)\/Z

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

51.  Формы существования информации – статическая или динамическая.

52.  Сегодня ясное небо и сильный мороз.

53.  Завтра ожидается мокрый снег или дождь с мокрым снегом.

54.  Билет на самолет можно купить в кассе или в Интер-нете.

55.  Если я буду хорошо учиться в институте, то буду бакалавром или магистром.

56.  Если информатика мне интересна, я буду ходить на все лекции по информатике.

57.  Автомобиль не заводится, если нет бензина или разряжен аккумулятор.

58.  После окончания института буду работать на фирме или поступлю в заочную аспирантуру и буду работать на этой фирме.

59.  Мобильный телефон можно подключить к компьютеру непосредственно через разъем USB или через модуль беспроводной связи BlueTooth, который подключается к разъему USB.

60.  На ЕГЭ учащийся сдает два обязательных экзамена, а также информатику или биологию (по выбору).

61.  Если у студента нет троек, он получает стипендию.

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

63.  Если у студента в дипломе нет троек и не более 25 процентов четверок, он получает диплом с отличием.

64.  ЭВМ первого поколения работали на электронных лампах и имели оперативную память.

65.  Если число оканчивается на 2 или 4, то оно четное.

66.  Если целое положительное число, большее 1, делится только на самого себя и единицу, то это простое число.

67.  Если число делится на 6, то число делится на 2 и на 3.

68.  Если число делится на 2 и на 5, то оно делится на 10.

69.  Если номер года делится без остатка на 4 и число сотен в номере года также делится на 4, то такой год называется високосным.

70.  Если треугольник имеет угол 90 градусов, то он прямоугольный.

71.  Если треугольник не имеет угла 90 градусов, то он остроугольный или тупоугольный.

72.  Если студент не выполнил необходимые практические задания, то он не допускается к сдаче экзамена.

73.  Если студент хорошо подготовился самостоятельно или если ему помог однокурсник, то он успешно сдаст зачет.

74.  Доехать до института я могу на метро и автобусом или на автобусе и троллейбусе.

75.  Компьютерные преступления без тяжких последствий наказываются лишением свободы на срок до трех лет и штрафом (до двухсот тысяч рублей или в размере заработной платы за период до восемнадцати месяцев).

Литература

Стол, Р. Множества, логика, аксиоматические теории / Р. Стол. – М., 1984.

Карасев, А. И. Курс высшей математики для экономических вузов / А. И. Карасев, , . – М., 1982.

Казанцев, С. Я. и др. Информатика и математика для юристов / С. Я. Казанцев, и др. – М., 2008.

Кудрявцев, В. А. Краткий курс высшей математики /
В. А. Кудрявцев, – М., 1989.

Маланин, И. Г. Практикум по курсу информатика и математика / , . – М. : АТиСО, 2007.

Оглавление

Введение. 3 Раздел 1. Аксиоматический метод. 4 Раздел 2. Предмет математической логики. 4 Раздел 3. Алгебра высказываний. 4 Раздел 4. Составление таблиц истинности. 4 Пример 1. 4 Использование логических функций EXCEL для составления таблиц истинности. 4 Раздел 5. Формализация высказываний. 4 Пример 2. 4 Пример 3. 4 Раздел 6.Тавтологии. 4 Пример 4. 4 Раздел 7. Равносильность формул логики высказываний. 4 Свойства отношения равносильности. 4 Законы логики высказываний. 4 Равносильные преобразования. 4 Литература. 4

3 4 10 12 18 19 20 21 21 22 23 23 24 25 25 26 30

, ,

МАТЕМАТИКА И ИНФОРМАТИКА

МАТЕМАТИКА. Часть 1

УЧЕБНОЕ ПОСОБИЕ

Редактор –

Компьютерная верстка –

Издательский дом «АТИСО»

 

Объем: 2,0 п. л.; 1,2 уч.-изд. л. Тираж 100 экз. Формат А5 Заказ № 000
Подписано в печать 11.01.2010 г. Отпечатано в типографии АТиСО

Адрес редакции: 119454, Москва,

Тел.: [phone], тел./

 

[1] Булева алгебра (алгебра логики, алгебра суждений) – раздел математики, в котором изучаются логические операции над высказываниями. Из всей логики именно Булева алгебра получила самое большое практическое применение в технике.