ДМ_Конспект

Конъюнктивное поглощение

C(C x) C , где C некоторая элементарная дизъюнкция переменных; x

булева переменная.

Кортеж

Совокупность конкретных значений аргументов булевой функции.

Линейная функция

Булева функция, которая представляется в алгебре Жегалкина каноническим многочленом (полиномом Жегалкина), не содержащем конъюнкций

переменных: 0 1 x1 2 x2 ... n xn , где коэффициенты	0 , 1 , 2 ,...,n ,
принимающие значение 0 или 1.
Логические переменные
То же, что и булевы переменные.
Логическая функция
То же, что и булева функция.

Макстерм k -го ранга

Член конъюнктивной нормальной формы, представляющий собой элементарную конъюнкцию k букв.

Макстерм n -го ранга

То же, что и конституента нуля.

Минимальная ДНФ (МДНФ) булевой функции

Одна из еѐ тупиковых ДНФ, которой соответствует наименьшее значение критерия минимизации (индекса простоты) ДНФ.

Минимальная КНФ (МКНФ) булевой функции

Одна из еѐ тупиковых КНФ, которой соответствует наименьшее значение критерия минимизации (индекса простоты) КНФ.

Минимально полный базис

Система функций называется минимально полным базисом, если удаление из неѐ любой функции превращает эту систему в неполную.

Минтерм k -го ранга

Член дизъюнктивной нормальной формы, представляющий собой элементарную конъюнкцию k букв.

Минтерм n -го ранга

То же, что и конституента единицы.

Монотонная функция

Функция f (x1 , x2 , ..., xn ) называется монотонной, если для любых двух наборов

(1 ,2 ,...,n )	и	(1 , 2 ,...,n ) ,	находящихся	в	отношении
предшествования	(нестрогого порядка),		имеет место	и	неравенство

f (1 ,2 ,...,n ) f (1 , 2 ,...,n ) .

Неполное дизъюнктивное склеивание

Ax Ax A Ax Ax , где A некоторая элементарная конъюнкция переменных; x булева переменная.

Неполное конъюнктивное склеивание

261

(C x)(C x) C(C x)(C x) , где C некоторая элементарная дизъюнкция

переменных; x булева переменная.

Несократимая полная система булевых функций,

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

Номер интерпретации (кортежа)

Десятичный эквивалент двоичного представления интерпретации.

Нулевой элемент (нуль)

Элемент 0 из множества B {0,1}.

Область определения булевой функции

Множество слов длины n , которые представляют собой всевозможные наборы

из n двоичных цифр и их общее количество равно 2n .

Ослаблено функционально полная система

Система функций { f1 , f2 ,..., fn ,...} из P2 , суперпозицией которых может быть

представлена любая функция из некоторого множества булевых функций и в которой допускаются константы 0 и 1.

То же, что и функционально полная система булевых функций в слабом

смысле. Отрицание

Функция f2 (x) x , равная 1, когда аргумент принимает значение 0, и равная 0

при аргументе 1.

Переключательная функция То же, что и булева функция.

Покрытие функции

Множество S , состоящее из импликант функции f , если каждое единичное значение функции f покрывается единицей хотя бы одной импликанты из

множества S .

Полином Жегалкина

Конечная сумма по модулю 2 попарно различных элементарных конъюнкций над множеством переменных {x1 , x2 , ..., xn }.

Полная система импликант функции

То же, что и покрытие функции.

Полная система имплицент функции

Множество S , состоящее из имплицент функции f , если каждое единичное значение функции f покрывается нулем хотя бы одной имплиценты из

множества S .

Полное дизъюнктивное склеивание

Ax Ax A, где A некоторая элементарная конъюнкция переменных; x булева переменная.

Полное конъюнктивное склеивание

262

(C x)(C x) C , где C некоторая элементарная дизъюнкция переменных; x

булева переменная.

Полностью определенная функция

Функция, зависящая от n аргументов, является полностью определенной, если указаны еѐ значения для всех наборов (кортежей, слов) значений элементов.

Принцип двойственности

Указывает правило получения двойственных формул в булевой алгебре.

Простая импликанта функции

Такая конъюнкция-импликанта, что никакая еѐ собственная часть не является импликантой данной функции.

Простая имплицента функции

Такая дизъюнкция-имплицента, что никакая еѐ собственная часть не является имплицентой данной функции.

Равносильные формулы

Формулы, представляющие одну и ту же функцию.

Ранг элементарной конъюнкции

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

Самодвойственная функция

Функция, двойственная сама себе, т.е. f f * .

Собственной частью конъюнкции B

Всякая элементарная конъюнкция A , входящая в состав элементарной конъюнкции B и содержащая меньше переменных, чем конъюнкция B .

Совершенная дизъюнктивная нормальная форма (СДНФ) булевой функции

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

Совершенная конъюнктивная нормальная форма (СКНФ) булевой функции

Формула, представленная в виде конъюнкции конституент нуля булевой функции.

Сокращенная дизъюнктивная нормальная форма (ДНФ)

Дизъюнкция всех простых импликант функции.

Сокращенная конъюнктивная нормальная форма КНФ

Конъюнкция всех простых имплицент функции.

Суперпозиция

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

Таблица истинности

Таблица, в которых каждой интерпретации (то есть набору аргументов) функции поставлено в соответствие еѐ значение.

Таблица соответствия То же, что и таблица истинности.

Тупиковая дизъюнктивная нормальная форма (ДНФ) булевой функции

263

ДНФ булевой функции, состоящая только из простых импликант.

Тупиковая дизъюнктивная нормальная форма (КНФ) булевой функции

КНФ булевой функции, состоящая только из простых имплицент.

Формула

Выражение, содержащее булевы функции и их суперпозиции.

Формула, реализующая (представляющая) функцию

Формула, которая задает булеву функцию.

Функционально полная система булевых функций

Система функций { f1 , f2 ,..., fn ,...} из P2 (где P2 − множество всех возможных

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

Функционально полная система булевых функций в слабом смысле

Система функций { f1 , f2 ,..., fn ,...} из P2 , суперпозицией которых может быть

представлена любая функция из некоторого множества булевых функций и в которой допускаются константы 0 и 1.

То же, что и ослаблено функционально полная система.

Функция, сохраняющая единицу (1)

Булева функция y f (x1, x2 , ..., xn ) , которая на единичном наборе равна 1, т.е. f (1, 1, ...,1) 1.

Функция, сохраняющая ноль (0)

Булева функция y f (x1, x2 , ..., xn ) , которая на нулевой наборе равна 0, т.е. f (0, 0, ...,0) 0.

Эквивалентные формулы

Формулы, представляющие одну и ту же функцию (то же, что и равносильные формулы).

Элементарная дизъюнкция

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

Элементарная конъюнкция

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

3.2 Логика высказываний и логика предикатов

n -местный предикат

Предикат, содержащий n переменных ( n аргументов) (обозначается

P(x1 , x2 ,...,xn )).

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

Аксиомами логики высказываний является некоторое множество общезначимых формул логики высказываний.

Антецедент

264

В импликации A B высказывание A называется антецедентом.

То же, что и условие, посылка.

Атом (в логике высказываний)

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

То же, что и элементарное высказывание, атомарная формула.

Атом (в логике предикатов)

Если P n -местный предикат и t1 ,t2 ,...,tn термы, то P(t1 ,t2 ,...,tn ) называется атомом.

То же, что и элементарная формула логики предикатов.

Атомарная формула То же, что и элементарное высказывание, атом.

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

Всякая последовательность	A1 , A2 ,..., An	формул такая, что для любого i
формула Ai есть либо	аксиома,	исчисления высказываний, либо

непосредственное следствие каких-либо предыдущих формул, полученных по правилу вывода.

Выполнимые формулы

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

Высказывание

Утверждение или повествовательное предложение, о котором можно сказать, истинно оно или ложно, но ни то и другое одновременно.

Высказывательная переменная

Переменная, которая может принимать два значения: «истина» и «ложь», т.е. принимать истинностное значение.

Двуместный предикат

Предикат, имеющий две переменные (может обозначаться, например, P(x, y) , где x, y − переменные).

Дедуктивный вывод

Вывод формулы B из формулы A , основанный на том, что B является логическим следствием A .

Дизъюнкция высказываний A и B

Высказывание A B , которое ложно тогда и только тогда, когда ложны оба высказывания A и B .

Дистрибутивные свойства кванторов

(Q1 x)F(x) (Q2 y)H ( y) (Q1 x)(Q2 y)(F(x) H ( y)) ; (Q1 x)F(x) (Q2 y)H ( y) (Q1 x)(Q2 y)(F(x) H ( y)) ,

где (Q1 x), (Q2 x) − любой из кванторов или .

Закон де Моргана для кванторов

((x)F(x) (x) F(x) ; ((x)F(x) (x) F(x) .

265

Закон замены связанной переменной

(x)F(x) (y)F( y) , (x)F(x) (y)F( y) .

Заключение

В импликации A B высказывание B называется заключением.

То же, что и следствие, консеквент.

Замкнутая формула

Формула логики предикатов, которая не имеет свободных переменных.

Импликация высказываний A и B

Высказывание A B , которое ложно тогда и только тогда, когда A истинно, а B ложно.

Индивидуальный символ

Терм-константа называется индивидуальным символом.

То же, что и предметная константа.

Интерпретация высказывания

Приписывание истинностных значений атомам, из которых построено высказывание.

Интерпретация формулы логики предикатов

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

Истинностное значение

Абстрактный объект («истина» или «ложь»), сопоставляемый высказыванию в зависимости от того, является это высказывание истинным или ложным. Обозначается: «истина» − И, Т (True) или 1, „ложь‖ – Л, F (False) или 0.

Исчисление высказываний

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

Исчисление предикатов

Формальная система в логике предикатов.

Квантор всеобщности

Символ называется квантором всеобщности.

То же, что и квантор общности.

Квантор общности То же, что и квантор всеобщности.

Квантор существования

Символ называется квантором существования.

Коммутативные свойства кванторов

(x)(y)P(x, y) (y)(x)P(x, y) ; (x)(y)P(x, y) (y)(x)P(x, y) .

Консеквент

В импликации A B высказывание B называется консеквентом.

То же, что и следствие, заключение.

266

Конъюнкция высказываний A и B

Высказывание A B , которое истинно тогда и только тогда, когда истинны оба высказывания A и B .

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

Алгебраическая структура ({Л, И}, , , , , ~,) ) с носителем – двоичным

множеством { Л : «Ложь», И : «Истина»}, операциями (логическими связками): « » – конъюнкция, « » – дизъюнкция, « » – отрицание, « » – импликация, «~» – эквивалентность.

Логическая эквивалентность

Отношение эквивалентности (оно рефлексивно, симметрично и транзитивно).

То же, что и равносильность.

Логическое следствие

Высказывание B является логическим следствием высказывания A , если формула A B является тождественно истинной. Высказывание B является логическим следствием высказываний A1 , A2 ,..., An , если A1 A2 ... An B −

тождественно истинная формула.

Множество истинностных значений

Множество {И, Л}.

Молекула

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

То же, что и формула в логике высказываний.

Невыполнимая формула

Формула, которая принимает значение «ложь» на всех интерпретациях.

То же, что и тождественно ложная формула или противоречивая формула.

Независимая система аксиом

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

Необщезначимая формула

Формула, которая на одних интерпретациях принимает значение «истина», а на других – «ложь».

То же, что и непротиворечивая формула.

Непротиворечивая формула То же, что и необщезначимая формула.

Непротиворечивое логическое исчисление

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

Нульместный предикат

Нульместным предикатом считается высказывание.

Область действия квантора

Формула P(x) в выражениях ( )P(x) и ( )P(x) , на которую

распространяется действие квантора.

267

Область значений предиката

Фиксированное множество {И, Л}.

Область определения предиката

Множество значений M , которое может принимать x в предикате P(x) .

То же, что универс или предметная область.

Общезначимая формула

Формула, которая принимает значение «истина» на всех интерпретациях (наборах значений переменных).

То же, что и тождественно истинная формула или тавтология.

Одноместный предикат

Предикат с одной переменной (может обозначаться, например, P(x) , где

x − переменная).

Отрицание высказывания A

Высказывание (обозначение A ), которое истинно тогда и только тогда, когда A ложно.

Порядок предиката

Количество аргументов предиката P(x1 , x2 ,...,xn ).

Посылка

В импликации A B высказывание A называется посылкой.

То же, что и условие, антецедент.

Правило введения квантора всеобщности

	P(c) для произвольного с D	утверждает истинность	xP(x) , если доказана
	xP(x)

истинность P(с) для любого c , то есть для всех элементов c из

рассматриваемой предметной области D .

Правило введения квантора существования

	P(c) для некоторого с D	позволяет заключить, что	xP(x)	является
	xP(x)

истинным, когда известен некоторый элемент c , для которого истинно P(с) .

Правило -введения То же, что и правило связывания квантором общности или правило

обобщения. Правило -введения

То же, что и правило связывания квантором существования

Правила вывода

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

Правило обобщения То же, что и правило связывания квантором общности или правило -

введения.

Правило отделения

268

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

Правило отделения в исчислении предикатов

Формулируется так же, как и в исчислении высказываний: P, P Q .

Q

Правило переименования связанной переменной.

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

Правило подстановки

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

Правило связывания квантором общности

	P Q(x)
			, где Q(x) содержит свободные вхождения x			, а P их не содержит.
	P Q(x)
То же, что и правило обобщения или правило -введения.
Правило связывания квантором существования
	Q(x) P
		, где Q(x) содержит свободные вхождения x , а P их не содержит.
	Q(x) P
То же, что и правило -введения.
Правило удаления квантора всеобщности
		xP(x)
				, где c	− произвольно	выбранный элемент
	P(c) для произвольного с D

предметной области D , в которой справедливо xP(x) .

Правило удаления квантора существования

	xP(x)	в истинной формуле	xP(x) заключается в указании
	P(c) для некоторого с D

имени элемента c (конкретного или гипотетического), для которого P(с)

истинно.

Правильно построенная формула (в логике высказываний)

В логике высказываний правильно построенная формула определяется рекурсивно следующим образом: атом есть формула; если A и B формулы, то (A B), (A B), (A B), (A ~ B), A также формулы; никаких формул, кроме порожденных указанными выше правилами, не существует.

Правильно построенная формула логики предикатов

Рекурсивно определяется следующим образом: атом является

формулой;	если	P	и	Q	−	формулы,	то
(P), (P Q), (P Q), (P Q), (P ~ Q) также являются формулами; если P
− формула, а	x −	свободная переменная,			то	(x)P и (x)P	тоже
			269

формулы; никаких формул, кроме порожденных указанными выше

правилами, не существует.

Правильное рассуждение

Рассуждение, которое выражается тождественно истинной формулой.

Предваренная нормальная форма

Формула F в логике первого порядка находится в предваренной нормальной форме (ПНФ) тогда и только тогда, когда она может быть представлена в виде (Q1 x1 )...(Qn xn )(A) , где каждое (Qi xi ) , i 1,...,n , есть или

(x) , или	(x) , а	A −	формула, не содержащая кванторов. Причем
(Q1 x1 )...(Qn xn ) называется префиксом, а A − матрицей формулы F .
Предикат
Функция P(x1 , x2 ,...,xn ),			переменные которой принимают значения из
некоторого	множества		M , а сама она принимает два значения			И
(истинное)	и Л	(ложное), т.е.		P(x , x ,...,x ) : M n {И, Л}		(где
				1 2	n

M n M M ... M ).

Предметная константа

Терм-константа называется предметной константой.

То же, что и индивидуальный символ.

Предметная область

Множество значений M , которое может принимать x в предикате P(x) .

То же, что область определения предиката или универс.

Предметная переменная

Терм-переменная называется предметной переменной.

Пропозициональная переменная То же, что и высказывательная переменная.

Противоречивая формула

Формула, которая принимает значение «ложь» на всех интерпретациях.

То же, что и тождественно ложная формула или невыполнимая формула.

Равносильность

Отношение эквивалентности (оно рефлексивно, симметрично и транзитивно).

То же, что и логическая эквивалентность.

Равносильные формулы

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

Свободная переменная

Переменная в предикатной формуле, не связанная никаким квантором.

Связанная переменная

Переход от P(x) к xP(x) или xP(x) называется связыванием переменной x , а сама переменная x в этом случае – связанной.

270