Элементы статистической обработки данных 4 страница

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

Импликация. Импликация – двуместная операция. Она задается табл.3.6, а записывается как

Y=x₁®x₀.

Правая часть этой записи читается так: если x₁, то x₀. В импликации переменная x₁ называется посылкой, а x₀ – заключением. Из табл.3.6 видно, что

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

Таблица 3.6		Таблица 3.7
x1	x0	Y		x1	x0	ùx1	ùx1Úx0

Логическую конструкцию импликации имеют математические теоремы.

Пример,

«Если два угла вертикальны, то они равны».

Здесь x₁ – два угла вертикальны, x₀ – они равны. Верности теоремы отвечает последняя строка табл. 3.6. Утверждение «Если два угла вертикальны, то они не равны» – ложно, а это – третья

строка табл. 3.6. Каждое из утверждений «Если два угла не вертикальны, то они равны» (строка вторая табл. 3.6) и «Если два угла не вертикальны, то они не равны» (первая строка табл. 3.6) может быть истинными или ложными. Но в импликации подобные утверждения однозначно определены как истинные.

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

Пример. «Если договор поднайма жилого помещения, предоставленного по договору социального найма, заключен без указания срока, сторона договора – инициатор прекращения договора обязана предупредить другую сторону о прекращении договора поднайма за три месяца» (ЖК РФ, ст. 79, ч.6).

Запишем импликацию в терминах функционально полной системы операций:

x₁®x₀=ùx₁Úx₀.

В верности этого равенства убедимся, если построим таблицу истинности для правой его части (табл. 3.7) и сравним ее выход с выходом табл. 3.6 для левой части. При построении табл. 3.7 мы использовали табл. 3.2 и табл.3.4.

Равнозначность. Равнозначность – многоместная операция. Для двух переменных она задается табл. 3.8. Как видим,

равнозначность истинна, когда все ее аргументы принимают одинаковые значения:

или все одновременно ложны,

или все одновременно истинны,

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

Обозначают равнозначность символом =:

Y=(x₁=x₀).

Правая часть этой записи читается так:

x₁ тогда и только тогда, когда x₀.

Любое равенство, если его рассматривать как одно высказывание, является равнозначностью. Например, Y=(2´2=5).

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

Y=(x_n-1=x_n-2=¼=x₀).

Синонимы для равнозначности:

x₁ в том, и только в том случае, когда x₀;

x₁ есть необходимое и достаточное условие для x₀;

x₀ есть необходимое и достаточное условие для x₁.

если x₁, то x₀, И если x₀, то x₁;

Последний из синонимов равнозначности позволяет выразить ее еще и так:

(x₁=x₀)=(x₁®x₀)Ù(x₀®x₁).

Читателю предлагается проверить верность этой формулы самостоятельно.

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

(x₁=x₀)=ùx₁Ùùx₀Úx₁Ùx₀.

Таблица 3.8

Таблица 3.9

x1

x0

Y

x1

x0

A

B

C

D

F

Пользуясь правилом о приоритетах логических операций, представим ФАЛ в правой части этого равенства такой цепочкой:

A=ùx₁, B=ùx₀, C=AÙB, D=x₁Ùx₀, F=CÚD.

Составим таблицу истинности для высказываний A, B, C, D и F (табл. 3.9), сравним ее выход с выходом табл. 3.8 и убедимся в верности представления равнозначности в терминах функционально полной системы операций алгебры логики.

Пример. В совершении преступления подозреваются И, П и С, которые дали такие показания:

И: Виновен П, а С – нет.

П: Если виновен И, то виновен и С (они всегда действуют сообща).

С: Я невиновен, но виновен хотя бы один из них.

Требуется а) установить виновного,

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

Обозначим простые высказывания о виновности подозреваемых: x₂ – виновен И, x₁ – виновен П, x₀ – виновен С. Тогда показания подозреваемых средствами алгебры логики запишутся так:

ПИ=x₁Ùùx₀, ПП=x₂®x₀, ПС=ùx₀Ù(x₂Úx₁),

а проверяемые импликации – так:

А=ПИ®ПП, Б=ПП®ПИ, В=ПП®ПС,

Г=ПС®ПП, Д=ПИ®ПС, Е=ПС®ПИ.

Составим таблицу истинности (табл. 3.10), в которой вспомогательные выражения – суть Н=ùx₀, Д=x₂Úx₁.

Таблица 3.10

Виновен

Вспом.

Показания

Импликации

a

x2

x1

x0

Н

Д

ПИ

ПП

ПС

А

Б

В

Г

Д

Е

а) Однозначный ответ получим, если предположить, что все подозреваемые говорят правду, и виноват П, а И, С – невиновны (строка 2 табл. 3.10).

Если же П говорит правду и невиновен, а И, С лгут (строки 0, 1, 3, 4 и 5), то виновны либо С, либо И, либо только С.

Последняя строка (все виновны): П говорит правду, а остальные снова лжесвидетельствуют.

б) Только одна импликация ПИ®ПС истинна при любых значениях ее посылки и заключения. Значит, показания подозреваемого И следуют из показаний П.

Такой анализ показаний подозреваемых позволяет спланировать дальнейшие следственные действия.

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

Пример. Возьмем такое высказывание:

«Уголовной ответственности подлежит лицо, достигшее ко времени совершения преступления шестнадцатилетнего возраста» (УК РФ, ст. 20, ч. 1).

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

Если лицо совершило преступление и ко времени его совершения оно достигло шестнадцатилетнего возраста, то это лицо подлежит уголовной ответственности.

И только после этого можно было бы изложить его так:

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

До сих пор мы имели дело со сложными высказываниями, в которых можно было выделить два-три простых утверждения. На практике приходится оперировать с более сложными высказываниями.

Пример. Приведем такое сложное высказывание (Y):

«Преступление признается совершенным с прямым умыслом, если лицо осознавало общественную опасность своих действий (бездействия), предвидело возможность или неизбежность наступления общественно опасных последствий и желало их наступления» (УК РФ, ст. 25, ч. 2).

Простые высказывания в нем:

§ преступление признается совершенным с прямым умыслом (x₀),

§ лицо осознавало общественную опасность своих действий (бездействия) (x₁),

§ лицо предвидело возможность наступления общественно опасных последствий своих действий (x₂),

§ лицо предвидело неизбежность наступления общественно опасных последствий своих действий (x₃),

§ лицо желало их наступления (x₄).

Эти простые высказывания (булевы переменные) связаны таким набором логических операций:

Y=(x₁Ù(x₂Úx₃)Ùx₄)®x₀.

Как видим, в этой формуле пять логических переменных, таблица истинности для нее будет иметь 2⁵=32 строки, и анализировать ее будет непросто. Правда, строить полную таблицу истинности для функции большого числа переменных необязательно. Можно узнать значение для Y в той или иной строке номер k, подставив в формулу значения аргументов в этой строке. Например, рассматриваемая импликация должна быть верной, когда верны ее посылка и заключение. Отметим, что в выражении для посылки дизъюнкция x₂Úx₃ (лицо предвидело возможность или неизбежность…) является квалификационным признаком для преступления с прямым умыслом, и она должна быть истинной. Поэтому проверяем значение импликации в строках с номерами a=31=1₄1₃1₂1₁1₀ (все единицы), a=27=1₄1₃0₂1₁1₀ и a=23=1₄0₃1₂1₁1₀:

Y(a=31)=(1₁Ù(1₂Ú1₃)Ù1₄)®1₀=1®1=1,

Y(a=27)=(1₁Ù(0₂Ú1₃)Ù1₄)®1₀=1®1=1,

Y(a=23)=(1₁Ù(1₂Ú0₃)Ù1₄)®1₀=1®1=1.

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

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

2.3. Аксиомы и теоремы алгебры логики

В булевой алгебре для любых высказываний A, B и C справедливы следующие аксиомы алгебры логики 1..5 и 1’..5’, а также и теоремы 6..12 и 6’..11’ (табл. 3.11). Для дизъюнкции и конъюнкции в булевой алгебре действуют законы коммутативные 1, 1’, ассоциативные 2, 2’ и дистрибутивные 3, 3’. Коммутативность операции позволяет располагать операнды в ней в произвольном порядке. Ассоциативность позволяет свести многоместную операцию к последовательности двуместных операций. Дистрибутивность позволяет выносить за скобки однородные члены или задает правило раскрытия скобок.

Таблица 3.11
	AÚB=BÚA			AÚBÚC=(AÚB)ÚC
1’	AÙB=BÙA		2’	AÙBÙC=(AÙB)ÙC
	AÚ(BÙC)=(AÚB)Ù(AÚC)			AÚ0=A
3’	AÙ(BÚC)=(AÙB)Ú(AÙC)		4’	AÙ1=A
	AÚùA=1			AÚ1=1
5’	AÙùA=0		6’	AÙ0=0
	AÚA=A			AÚ(AÙB)=A
7’	AÙA=A		8’	AÙ(AÚB)=A
	(AÙB)Ú(AÙùB)=A			ù(AÚB)=ùAÙùB
9’	(AÚB)Ù(AÚùB)=A		10’	ù(AÙB)=ùAÚùB
	ù0=1			ùùA=A
11’	ù1=0

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

Таблица 3.12
A	B	ùA	AÙB	AÚB	A®B	(A=B)

Таблицы, которые задают операции алгебры логики, тоже по сути своей аксиомы. Заменим в этих таблицах логические переменные произвольными высказываниями A и B и сведем их в одну общую табл. 3.12. Приоритеты этих операций убывают в таком порядке: отрицание, конъюнкция, дизъюнкция, импликация, равнозначность.

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

A®B=ùAÚB (3.1)

(A=B)=ùAÙùBÚAÙB (3.2)

Каждая из теорем легко доказывается с помощью табл.3.10 и табл. 3.12. Так, утверждение 12, которое называется законом двойного отрицания, доказывается непосредственной проверкой (табл.3.13).

Пример. Высказывание

«Неправда, что математика юристу не нужна»

не что иное, как двойное отрицание исходного утверждения

«Математика юристу нужна».

Утверждения 9 и 9’ называются законами склеивания. Докажем второе из этих утверждений:

(AÚB)Ù(AÚùB)=á3ñ=AÚ(BÙùB)=á5’ñ=AÚ0=á4ñ=A.

Таблица 3.13
A	B=ùA	C=ùB=ùùA

Читателю предложим самостоятельно доказать утверждения 10 и 10’, которые называются правилами де Моргана (по имени шотландского математика и логика Огюста де Моргана, первого президента Лондонского математического общества).

Мы же проиллюстрируем одно из этих правил таким примером. Про кого-то говорят: «Ни рыба, ни мясо!». Средствами логики эта фраза строится так: (он НЕ рыба) И (он НЕ мясо). Легко видеть, что это правая часть тождества 10. Ту же мысль можно сформулировать иначе: НЕПРАВДА, что (он рыба ИЛИ он мясо). А эта конструкция – суть левая часть тождества 10.

Приведенные тождества 1..11, 1’..11’ и 12 можно использовать для эквивалентных преобразований аналитических выражений и для доказательства любых других утверждений алгебры логики. Однако в табл. 3.10 нет операций импликации и равнозначности. Поэтому прежде чем воспользоваться этими тождествами, в исходном выражении необходимо с помощью формул (3.1) и (3.2) выразить импликации и равнозначности в терминах функционально полной системы операций.

Пример. Докажем аналитически истинность утверждения о том, что показание ПС=ùx₀Ù(x₂Úx₁) вытекает из показания ПИ=x₁Ùùx₀:

x₁Ùùx₀®ùx₀Ù(x₂Úx₁)=á(3.1), 3’ñ=

=ù(x₁Ùùx₀)Ú(x₂Ùùx₀)Ú(x₁Ùùx₀)=á5ñ=1Ú(x₂Ùùx₀)=á6ñ=1.

До сих пор мы получали ФАЛ путем анализа в сложных высказываниях логических связок типа И, ИЛИ, ЕСЛИ, ТО. Существуют способы получения ФАЛ из таблиц истинности, которые строят по результатам анализа высказываний.

Пример. Жюри из трех человек Ж2, Ж1, Ж0 принимает решение большинством голосов. При этом каждый член жюри может голосовать либо «за», либо «против». Опишем средствами алгебры логики все возможные результаты голосования. Для этого каждому из членов жюри поставим в соответствие свою логическую переменную Ж2=x₂, Ж1=x₁, Ж0=x₀,, которая принимает значение 0, если он голосует «против», и значение 1, когда он голосует «за». Результат голосования – логическая переменная Y. Она принимает значение 0, если решение не принимается, и значение 1, если оно принимается.

Таблица 3.14
x2	x1	x0	Y

А теперь составим таблицу истинности для такой ФАЛ (табл. 3.14). Колонки для x₂, x₁ и x₀ заполняем по описанному выше правилу, а Y равен 1 тогда, когда хотя бы два из трех аргументов равны 1 (хотя бы два из трех членов жюри голосуют «за»).

Рассмотрим один из возможных способов получить из таблицы истинности аналитическое выражение для Y, а именно, «построение формулы по единицам». Для этого выделим в табл. 3.14 те строки, в которых Y=1, и составим для каждой из этих строк конъюнкцию всех аргументов. При этом переменная x_k (k={2,1,0}) входит в такую конъюнкцию прямо (как x_k), если в данной строке x_k=1, если же здесь x_k=0, то она входит в конъюнкцию под знаком инверсии (как ùx_k). Полученные конъюнкции объединим операцией дизъюнкции. Так получим ФАЛ для Y:

Y=(ùx₂Ùx₁Ùx₀)Ú(x₂Ùùx₁Ùx₀)Ú(x₂Ùx₁Ùùx₀)Ú(x₂Ùx₁Ùx₀).

Пользуясь эквивалентностями алгебры логики, это выражение можно упростить:

Y=á7ñ=(ùx₂Ùx₁Ùx₀)Ú(x₂Ùùx₁Ùx₀)Ú(x₂Ùx₁Ùùx₀)Ú

Ú(x₂Ùx₁Ùx₀)Ú(x₂Ùx₁Ùx₀)Ú(x₂Ùx₁Ùx₀)=á2, 9, 6’ñ=

=(x₁Ùx₀)Ú(x₂Ùx₀)Ú(x₂Ùx₁).

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

Аналитическое выражение, построенное по единицам таблицы истинности для ФАЛ, называется совершенной дизъюнктивной нормальной формой СДНФ. СДНФ – канонический (стандартный) способ задания ФАЛ. Любой логической функции отвечает одна и только одна таблица истинности, а значит, и одна и только одна СДНФ. Обычно СДНФ допускает упрощения (как это былов в нашем примере), результатом которых будет формула с меньшим объемом вычислений.

Любую ФАЛ можно преобразовать к СДНФ. Для этого ее сначала, пользуясь теоремами и аксиомами алгебры логики, представляют дизъюнкцией конъюнкций. А потом каждое слагаемое умножают на такую дизъюнкцию (x_mÚùx_m) того сомножителя x_m, которого нет в этом слагаемом.

Пример. Развернем в СДНФ выражение для импликации в терминах функционально полной системы операций:

x₁®x₀=ùx₁Úx₀=ùx₁Ù(x₀Úùx₀)Úx₀Ù(x₁Úùx₁)=á3’, 1, 7ñ=

=(ùx₁Ùùx₀)Ú(ùx₁Ùx₀)Ú(x₁Ùùx₀).

Отметим, что последнюю формулу можно построить по единицам табл. 3.6, что мы предложим сделать читателю.

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

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

(((У®В)ÙУ)®В)=1.

Сначала упростим посылку второй импликации:

(У®В)ÙУ=á(3.1)ñ=(ùУÚВ)ÙУ=á3^’ñ=

=(ùУÙУ)Ú(ВÙУ)=á5^’ñ=0ÚВÙУ=á4,1ñ=УÙВ.

Следовательно,

(((У®В)ÙУ)®В)=((УÙВ)®В)=á(3.1)ñ=

=(ù(УÙВ)ÚВ)=á10^’ñ=ùУÚùВÚВ=á5,6ñ=1.

Значит, логически формулировка закона достаточного основания верна.

Таблица 3.15
Не A, или то, что получится в результате вставки частицы «не» перед глаголом в предложении A. Не верно, что A. A не имеет места A.	ùA
A и B. Не только A, но и B. Как A, так и B. A вместе с B. B, хотя и A. B, несмотря на A. A, в то время как B.	AÙB
A или B. Или A, или B, или оба. A и/или B. A, если не B.	AÚB
Если A, то B. В случае A имеет место B. Для A необходимо B. B имеет место в случае A. B, если A.	A®B
A если и только если B. Если A, то B, и наоборот. A, если B, и B, если A. Для A необходимо и достаточно B. A эквивалентно B. A тогда и только тогда, когда B.	A=B
Ни A, ни B.	ùAÙùB
Или A, или B, но не оба вместе. Либо A, либо B, но не оба вместе.	AÙùB Ú ùAÙB

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

Переводя выражения обычного языка на язык алгебры логики, мы иногда теряем некоторые оттенки смысла, но зато выигрываем в точности анализа. Так, утверждения AÙB и BÙA в алгебре логики абсолютно одинаковы в силу аксиомы 1^’. А вот фразы «У Джейн родился ребенок (A), и она вышла замуж (B)» и «Джейн вышла замуж (B), и у нее родился ребенок (A)» понимаются по-разному. Здесь порядок сомножителей в конъюнкциях воспринимается как следование их во времени. А в алгебре высказываний время не является аргументом в логических формулах. Перевод же той и другой фразы посредством AÙB или BÙA, соответственно, прост и достаточен для логического анализа, тем более что в этих фразах действительно нет идеи времени.

Дата добавления: 2014-11-18