§2. ОСНОВЫ ЛОГИКИ И ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА

1. Вопросы, подлежащие исследованию:

Логика. Алгебра множества. Высказывание. Предикаты. Логические функции. Аксиомы алгебры предикатов. Таблица истинности.

2. Краткий теоретический материал

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

Алгеброй множества называется некоторая совокупность определенных элементов X, с заданными

над ними определенными операциями f (часто

определяемые по сходству с операциями сложения и умножения чисел), которые удовлетворяют определенным свойствам – аксиомам алгебры.

Утверждение (высказывательная форма) – основная единица, неделимая с точки зрения отражения смысла информации.

Высказывание – это форма мышления, выраженная с помощью понятий, посредством которой что-либо утверждают или отрицают о предметах, их свойствах и

32

отношениях между ними. Высказывание может быть истинным или ложным, "true" или "fаlse", "1" или "0".

Переменная, значениями которой могут быть лишь значения "1" или "0", называется логической переменной или булевой переменной.

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

Логической (булевой) функцией f(х) называется

некоторая функциональная зависимость, в которой аргумент х – логическая переменная с заданным

множеством изменений аргумента, а значения функции f(x) берутся из двухэлементного множества R(f) = {1,0}.

Множество логических переменных x, y X с

определенными над ним операциями:	x	– отрицания
или инверсии, x y – логического	сложения		или
дизъюнкции, x y – логического умножения			или

конъюнкции называется алгеброй предикатов (и

высказываний), если эти операции удовлетворяют следующим аксиомам:

∙двойное отрицание: x = x

∙переместительность операндов:

x y = y x, x y = y x

33

∙	переместительность операций					дизъюнкции и
	конъюнкции:
	(x y) z = x (y z), (x y) z = x ( y z)
∙	одинаковые операнды: x x = x,					x x = x
∙	поглощения: x (x y) = x,			x (x y) = x
∙	распределения операции:			x ( y z) = (x y) (x z),
				x ( y z) = (x y) (x z)
∙	де Моргана:		= x y,		= x y
		x y		x y
∙	нейтральности: x ( y y) = x, x ( y y) = x

∙существования единицы (true, 1) и нуля (false, 0),

причем, 0 =1, 1 =0, x x =1, x x =0

Операции, определяющиеся совмещенной таблицей значений, представленного ниже вида называется

таблицей истинности

x	y	x	x y	x y
0	0	1	0	0
0	1	1	0	1
1	0	0	0	1
1	1	0	1	1

В логических формулах определено старшинство операций, например: скобки, отрицание, конъюнкция,

дизъюнкция.

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

34

Цель: Рассмотреть основные понятия и сведения алгебры высказываний и предикатов – высказывания, предикаты, аксиомы, логические выражения и функции.

После выполнения работы необходимо

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

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

Объем работы 2 часа

ЗАДАНИЯ К ПРАКТИЧЕСКОЙ РАБОТЕ

Решите следующие примеры:

1.Приведите примеры понятий, суждений, умозаключений и доказательств из различных наук: математики; информатики; физики и химии.

2.При каких значениях числа X предикат первого порядка не ((X > 8) или (X < –3)) примет значение:

а) ложь;

35

б) истина?

3.Какие предикаты первого порядка описывают условие: «Точка X не принадлежит отрезку [А;B]»?

а) не (X >А) и X < В;

б)Х<А или Х>В;

в) не (Х<В или Х>А);

г) Х<А и Х>В.

4.Изобразите в декартовой прямоугольной системе координат область, в которой и только в которой истинны следующие предикаты второго порядка:

а) (У > X) и (У +X> 0) и (У < 1);

5.Найдите значения логических выражений:

1)(x x) (x y) ;

2)((x y) x) x ;

3)( y x) (x y) ;

4)( y x) x ;

5)x (x x) x ;

6)((x y) (x x) ( y x) ;

7)((x y) (x y) x ;

8)((x x) y) ( y x) ;

9)(( y y) y) (x x) .

6.Даны два простых высказывания:

36

А={2–2=4}, В ={2–2=5}.

Какие из составных высказываний истинны: а) А; б) Б; в) А В; r) AvB.

7. Даны простые высказывания: А={5>3}, В={2=3} и С={4<2}.

Определите истинность составных высказываний:

а) (AvB) C => (A C)v(B C);	б) (A P)vC
<=> (AvC) (A B)).

8.Даны простые высказывания:

А={Принтер — устройство ввода информации}, Б={Процессор — устройство обработки информации}, С={Монитор — устройство хранения информации}, D={Клавиатура — устройство ввода информации}.

Определите истинность составных высказываний:

a) (A B) (CvD); б) (А В)=>(В С); в) (AvB)<(C D).

37

9.Дано составное высказывание не (не А и В), где А и В — простые высказывания. В каком случае данное высказывание будет ложным?

10.Выполните поразрядное логическое сложение двоичных чисел:

а) 100 110; б) 1010 1000; в) 101010 111111.

4.Рекомендации студентам по подготовке к работе с указанием литературы.

Для подготовки к выполнению лабораторной работы необходимо предварительное изучение теоретического материала в объеме, достаточном для проведения осмысленной работы при выполнении поставленной задачи – практического знакомства с основными понятиями информатики (основы логики и высказываний).

ЛИТЕРАТУРА

1.Информатика : учебник/ Б.В. Соболь [и др.]-Изд. 3-е, дополн. и перераб. — Ростов н/Д: Феникс, 2007.

— 446 [1] с.-(Высшее образование).

2.Могилев А. В. Практикум по информатике: Учеб. пособие для студ. высш. учеб. заведений /А.В.Могилев, Н.И.Пак, Е.К.Хеннер; Под ред. Е.К.Хеннера. — 2-е изд., стер. — М.: Издательский центр «Академия», 2005. — 608 с

3.Угринович Н.Д. Практикум по информатике и информационным технологиям. Учебное пособие

38

для общеобразовательных учереждений. Издание 2- е исп./Н.Д. Угринович, Л.Л. Босова, Н.И. Михайлова. М.:БИНОМ, 2004. 394 с.

4.Лабораторный практикум по информатике:

Учебное пособие для вузов/В.С. Микшина, Г.А. Еремеева, Н.Б. Назина и др.; Под ред. В.А. Острейковского. — М.: Высш. шк., 2003. — 376 с: ил.

5.Чеботарев С.В. Теория множеств. Учебное пособие/ С.В.Чеботарев БГПУ, 2004

6.Информатика.: Учебное пособие/ А. Н. Степанов. 3-е изд. — СПб.: Питер, 2002. — 608 с.: ил.

7.Каймин В.А. Информатика: Учебник./ В.А. Каймин - М.: ИНФРА-М,2000. - 232 с. - (Серия «Высшее образование»).

5. Темы рефератов:

1.Логические функции.

2.Предикаты.

39