Слово "логика" происходит от древнегреческого "логос", имеющего значения: слово, наука, разум

Вид материала

Содержание

Основателем логики
Джордж Буль
Основные понятия
Высказывательная форма
4. Приоритет логических операций
Алгебра логики
1. Логическая переменная
2. Функции в алгебре логики
Логические операции
таблица истинности
1. Таблицы истинности функции одной переменной
2. Таблицы истинности функции двух переменных.
3. Как построить таблицу истинности логической функции, содержащей более одной логической связки.
4. Законы алгебры логики
Основные законы алгебры логики
A&(b&c) = (a&b)&c = a&b&c
Справедливость любого закона АЛ можно доказать разными методами.
Основные тождества
Основные правила
Вычисление логических функций
...
Полное содержание

Подобный материал:

ЛОГИКА

ИСТОРИЯ ЛОГИКИ

Слово "логика" происходит от древнегреческого "логос", имеющего значения: слово, наука, разум. Поэтому оно, во-первых, вошло составной частью в названия многих наук, а во-вторых, выражает смысл логики, как НАУКИ О МЫСЛЯХ.

   Родословная логики связана с философскими размышлениями о правилах спора и процедурах убеждения, поэтому сначала логика была скорее вспомогательной частью риторики и юриспруденции. Так было до Аристотеля. Развитие науки логики на протяжении ряда столетий протекало по двум направлениям. Одно из них начиналось с древнегреческой логики (в особенности с логики Аристотеля), на основе которой развивалась логика в Древнем Риме, затем Византии, Турции, Армении, арабоязычных странах Ближнего Востока, в Западной Европе и России. Другое направление имело своим истоком индийскую логику, на основе которой развивалась логика в Китае, Тибете, Монголии, Корее, Японии, Индонезии, на Цейлоне.

    Основателем логики, как науки, считают Сократа (469-399 гг до н.э.). На первый план он выдвинул проблему метода, посредством которого можно получить истинное знание. Сократ считал, что любой предмет может быть познан лишь в том случае, если его можно свести к общему понятию и судить о нем на основе этого понятия. Познание "по Сократу" происходило следующим образом. На площади собиралось большое количество людей. Сократ просил их дать определение какого-либо понятия (например, " справедливость"). Выслушивая определения одно за другим, он показывал несовершенство каждого, каждый раз требуя более полного и точного. Таким образом, приближаясь к верному определению понятия, люди приближались к "ПОЗНАНИЮ " этого понятия. ЗНАНИЕ для Сократа - это ПОНЯТИЕ О ПРЕДМЕТЕ, и достигается оно посредством ОПРЕДЕЛЕНИЯ понятия.

Аристотель (384-322 гг до н.э.) - отец европейской логической традиции, разработавший СПОСОБЫ ПОСТРОЕНИЯ УМОЗАКЛЮЧЕНИЙ (силлогизмов) И ИХ ОЦЕНКИ. Его дед - легендарный древнегреческий врач Асклепий (отсюда "эскулап"). Отец Аристотеля - тоже врачеватель, вылечил Филиппа, сына Фракийского царя, будущего отца Александра Македонского. Аристотель был дружен с Филиппом, обучался наукам в академии Платона. После смерти великого учителя он переехал в Афины. Там Аристотель взялся за создание собственного учебного заведения, которое располагалось рядом с городским садом и от этого получило название "ликей" (сад). Что Вам напоминает это слово? Аристотель преподавал, прогуливаясь с учениками по саду. Такой метод назывался "схолэ". А на что похоже это слово?

Позднее из логики стала выделяться самостоятельная часть - математическая логика, изучающая основания математики и принципы построения математических теорий. У ее истоков стоял великий Лейбниц. Мат. логика - логика умозаключений, использующая математические методы. В момент возникновения эта наука была очень абстрактной, отвлеченной, доступной только узкому кругу ученых.

Так было до того момента, когда в XIX веке англичанин Джордж Буль (Boole) (1815-1864) пошел на спор, что создаст науку, совершенно оторванную от действительности и не имеющую ни малейшего практического применения. Он превратил мат. логику в АЛГЕБРУ СУЖДЕНИЙ. Булева алгебра - наука о действиях над суждениями (высказываниями). Буль произвел революцию в науке, о которой сам не подозревал. То, во что он превратил логику, было в дальнейшем положено в основу построения электронно-вычислительных устройств. История показала, что спор Булем был проигран. Из всей логики именно Булева алгебра получила самое большое практическое применение в технике. С именем Джорджа Буля связано еще одно известное имя: его дочь - Э. Войнич (Вы, наверное, читали ее роман "Овод"). Важнейшим разделом мат. логики, который сейчас перерастает в самостоятельную науку, является ТЕОРИЯ АЛГОРИТМОВ.

Дальнейшее усовершенствование алгебры логики было осуществлено английским логиком У.С. Джевонсом (1835-1882), немецким логиком Э. Шредером (1841-1902), русским логиком П.С. Порецким (1846-1907) и другими.

В последующих трудах по алгебре логики немецкого логика Г. Фреге (1848-1925), разработавшего теорию исчисления высказываний, немецкого логика и математика Д. Гильберта (1862-1943), английского философа и логика Б. Рассела (1872-1970), придавшего (вместе с Уайтхедом) математической логике современный вид, русского логика и математика И.И. Жегалкина (1869-1947), заслугой которого явилась дальнейшая разработка исчисления классов и значительное упрощение теории операций логического сложения, предмет алгебры логики вышел далеко за рамки изучения обычных операций с понятиями.

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

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

Строгие доказательства применимости булевой алгебры в теории контактных и релейно-контактных схем были даны в 1938 году русским физиком В.И. Шестаковым и американским математиком К.Э. Шенноном.

Область логических методов анализа и синтеза схем бурно развивалась в 50-е и начале 60-х годов и к середине 60-х годов стала сложившейся научной дисциплиной с развитым аппаратом и определенной областью исследований.

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

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

ОСНОВНЫЕ ПОНЯТИЯ

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

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

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

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

(пример. Прямоугольник, проливной дождь, компьютер)

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

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

(Пример. Истинное высказывание: «Буква «а» - гласная.». Ложное высказывание: «Компьютер был изобретен в середине 19 века».)

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

(Пример. Дано высказывание: «Все углы равнобедренного треугольника равны.» Получить высказывание «Этот треугольник равносторонний» путем умозаключений.)

ВЫСКАЗЫВАНИЕ

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

Логическое высказывание — это любое повествовательное пpедлoжение, в oтнoшении кoтopoгo можно oднoзначнo сказать, истинно oнo или лoжнo.

Пример:

“6 — четное число” - это истинное высказывание.
“Рим — столица Франции” - ложное высказывание.

Разумеется, не всякое предложение является логическим высказыванием. Высказываниями не являются, например, предложения “ученик десятого класса” и “информатика — интересный предмет”. Первое предложение ничего не утверждает об ученике, а второе использует слишком неопределённое понятие “интересный предмет”. Вопросительные и восклицательные предложения также не являются высказываниями, поскольку говорить об их истинности или ложности не имеет смысла.

Заметим, что зачастую трудно установить истинность высказывания. Так, например, высказывание “площадь поверхности Индийского океана равна 75 млн кв. км” в одной ситуации можно посчитать ложным, а в другой — истинным. Ложным — так как указанное значение неточное и вообще не является постоянным. Истинным — если рассматривать его как некоторое приближение, приемлемое на практике.

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

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

2. Виды высказываний

Высказывание может быть простым или сложным.

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

Употребляемые в обычной речи слова и словосочетания "не”, “и”, “или”, “если... , то”, “тогда и только тогда” и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

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

Элементарное высказывание рассматривается как неделимая единица.

Так, например, из элементарных высказываний “Петров — врач”, “Петров — шахматист” при помощи связки “и” можно получить составное высказывание “Петров — врач и шахматист”, понимаемое как “Петров — врач, хорошо играющий в шахматы”.

При помощи связки “или” из этих же высказываний можно получить составное высказывание “Петров — врач или шахматист”, понимаемое в алгебре логики как “Петров или врач, или шахматист, или и врач и шахматист одновременно”.

Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Чтобы обращаться к логическим высказываниям, им назначают имена. Пусть через А обозначено высказывание “Тимур поедет летом на море”, а через В — высказывание “Тимур летом отправится в горы”. Тогда составное высказывание “Тимур летом побывает и на море, и в горах” можно кратко записать как А и В. Здесь “и” — логическая связка, А, В — логические переменные, которые мoгут принимать только два значения — “истина” или “ложь”, обозначаемые, соответственно, “1” и “0”.

3. Логические связки

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение:

(1) Операция, выражаемая словом “не”, называется отрицанием и обозначается чертой над высказыванием (или знаком  ). Высказывание A истинно, когда A ложно, и ложно, когда A истинно. Пример. “Луна — спутник Земли” (А); “Луна — не спутник Земли” (A).

(2) Операция, выражаемая связкой “и”, называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой "•" (может также обозначаться знаками или &). Высказывание А•В истинно тогда и только тогда, когда оба высказывания А и В истинны.

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

“10 делится на 2 и 5 больше 3”

истинно, а высказывания

“10 делится на 2 и 5 не больше 3”,
“10 не делится на 2 и 5 больше 3”,
“10 не делится на 2 и 5 не больше 3”

ложны.

(3) Операция, выражаемая связкой “или” (в неразделительном, неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны.

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

“10 не делится на 2 или 5 не больше 3”

ложно, а высказывания

“10 делится на 2 или 5 больше 3”,
“10 делится на 2 или 5 не больше 3”,
“10 не делится на 2 или 5 больше 3”

истинны.

(4) Операция, выражаемая связками “если ..., то”, “из ... следует”, “... влечет ...”, называется импликацией (лат. implico — тесно связаны) и обозначается знаком =>. Высказывание А => В ложно тогда и только тогда, когда А истинно, а В — ложно.

Каким же образом импликация связывает два элементарных высказывания? Покажем это на примере высказываний: “данный четырёхугольник — квадрат” (А) и “около данного четырёхугольника можно описать окружность” (В). Рассмотрим составное высказывание А В, понимаемое как “если данный четырёхугольник квадрат, то около него можно описать окружность”. Есть три варианта, когда высказывание А =>В истинно:

А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;
А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);
A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность.

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

В обычной речи связка “если ..., то” описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться “бессмысленностью” импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, такими:

“если президент США — демократ, то в Африке водятся жирафы”,
“если арбуз — ягода, то в бензоколонке есть бензин”.

(5) Операция, выражаемая связками “тогда и только тогда”, "необходимо и достаточно”, “... равносильно ...”, называется эквиваленцией или двойной импликацией и обозначается знаком <=> или ~ . Высказывание А <=> В истинно тогда и только тогда, когда значения А и В совпадают.

Например, высказывания

“24 делится на 6 тогда и только тогда, когда 24 делится на 3”,
“23 делится на 6 тогда и только тогда, когда 23 делится на 3”

истинны, а высказывания

“24 делится на 6 тогда и только тогда, когда 24 делится на 5”,
“21 делится на 6 тогда и только тогда, когда 21 делится на 3”

ложны.

Итак, нами рассмотрены пять логических операций: отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция.

Импликацию можно выразить через дизъюнкцию и отрицание: А · В = Аv В. Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию: А « В = (Аv В) • (Вv А).

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

4. Приоритет логических операций

Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания (“не”), затем конъюнкция (“и”), после конъюнкции — дизъюнкция (“или”) и в последнюю очередь — импликация.

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

имеют одинаковые значения.

ЛОГИКА ВЫСКАЗЫВАНИЙ, раздел логики, в котором вопрос об истинности или ложности высказываний рассматривается и решается на основе изучения способа построения высказываний из т.н. элементарных (далее не разлагаемых и не анализируемых) высказываний с помощью логических операций конъюнкции ("и"), дизъюнкции ("или"), отрицания ("не"), импликации ("если..., то...") и др. Логику высказываний, задаваемую системой постулатов (аксиом и правил вывода), называют исчислением высказываний.

АЛГЕБРА ЛОГИКИ

Алгебра логики — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.

Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.

1. Логическая переменная

Логическая переменная в алгебре логики может принимать одно из двух возможных значений: TRUE - истина, FALSE - ложь. Эти значения в цифровой технике принято рассматривать как логическую "1" (TRUE) и логический "0" (FALSE), или как двоичные числа 1 и 0. Физически это может означать присутствие или отсутствие некоторого сигнала (замкнуто, разомкнуто), уровень потенциала на электронном элементе (высокий, низкий), протекание или отсутствие тока в некоторой цепи и т.п. Логические переменные позволяют легко описать состояние таких объектов, как тумблеры, кнопки, реле, триггеры и других, которые могут находиться в двух четко различимых состояниях: включено - выключено.

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

Логические переменные обозначают заглавными латинскими буквами: A, B, C, D,... Логические переменные можно заменять конкретными по содержанию высказываниями.

2. Функции в алгебре логики

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

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

Логические операции:

	Отрицание
& ,	Конъюнкция
V , +	Дизъюнкция
=>	Импликация
<=>	Эквивалентность

Обычно значения логических функций записываются в виде таблиц (т.н. таблицы истинности). Число строк в такой таблице - это число возможных наборов значений аргументов. Оно равно 2ⁿ, где n - число переменных. Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.

3. Таблицы истинности

1. Таблицы истинности функции одной переменной

Таблица истинности функции одной переменной Y=f(A) содержит всего 2 строки

Существует 4 различные логические функции одной переменной. Вот одна из них: (отрицание переменной)

A	A
1	0
0	1

2. Таблицы истинности функции двух переменных.

Известному немецкому математику и логику Эрнесту Шредеру пришло в голову предложить в качестве знака для обозначения ложного суждения цифру О, что, конечно, привело к обозначению истины цифрой 1. Тогда таблица истинности приобретает некий арифметический вид. Составим таблицу истинности, в которой представлены значения функций двух переменных, связанных различными логическими связками:

A	B	A&B	AVB	A=>B	A<=>B
0	0	0	0	1	1
0	1	0	1	1	0
1	0	0	1	0	0
1	1	1	1	1	1

Здесь А и В - логические переменные, а

A&B

AVB

A=>B

A<=>B

- логические функции f(A,B)

Итак, для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0,0),   (0,1),   (1,0),   (1,1).

Если формула содержит три переменные, то возможных наборов значений переменных восемь:

(0,0,0),   (0,0,1),   (0,1,0),   (0,1,1),

(1,0,0),   (1,0,1),   (1,1,0),   (1,1,1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.

3. Как построить таблицу истинности логической функции, содержащей более одной логической связки.

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

Здесь необходимо помнить, что существует приоритет логических операций: действия в скобках, отрицание щ, конъюнкция (и &), дизъюнкция (или V), импликация =>, эквиваленция.<=>

Пример. Построить таблицу истинности для логической функции y= v  A&C

Переменные			Промежуточные логические формулы					Функция
A	B	C				 A	 A&C	v  A&C
0	0	0	1	1	0	1	0	0
0	0	1	1	1	0	1	1	1
0	1	0	0	0	1	1	0	1
0	1	1	0	0	1	1	1	1
1	0	0	1	1	0	0	0	0
1	0	1	1	1	0	0	0	0
1	1	0	0	1	0	0	0	0
1	1	1	0	1	0	0	0	0

4. Законы алгебры логики

В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений:

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

Закон	ИЛИ	И
Переместительный (Коммутативный)	A v B = B v A.	A & B = B & A;
Сочетательный (Ассоциативный)	A v (BvC) = (AvB) v C = A v B v C.	A&(B&C) = (A&B)&C = A&B&C;
Распределительный (Дистрибутивный)	A v B&C = (A v B)&(A v C).	A&(B v C) = A&B v A&C;
Правила де Моргана	(A v B) == A & B	v B
Идемпотенции	A v A == A	A & A == A
Поглощения	A v (B & A) == A	A & (B v A) == A
Склеивания	(A & B) v (A & B) == A	(A v B) & (A v ) == A
Операция переменной с ее инверсией	A v 	A & 
Операция с константами	A v 0 = A, A v 1=1	A & 0=0, A&1=1
Двойного отрицания	

Все формулы, за исключением последней, при замене "&" на знак умножения и "v" на знак сложения превращаются в знакомые арифметические формулы перестановки, сочетания и распределения.

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

Рассмотрим пример:

Доказать справедливость закона поглощения.

A&(AvB) = A&AvA&B = AvA&B =A&1vA&B = A&(1vB) = A&1 = A.

и еще один...

Av(A&B) = A&1vA&B = A&(1vB) =A&1 = A.

В этой алгебре справедливы следующие основные соотношения, тождества, правила и законы.

Основные соотношения:

0 0 = 0,	0 0 = 0,
0 1 = 0,	0 1 = 0,
1 0 = 0,	1 0 = 0,	,
1 1 = 1,	1 1 = 1,	.

Основные тождества:

x 0 = 0,	x 0 = 0
x 1 = 1,	x 1 = 1
,
x  x ... x ,	,	.

Основные правила:

а) правило де Моргана:

б) конъюнктивное поглощение (x ₁ поглощает x ₁

x ₂):

в) дизъюнктивное поглощение (x ₁ поглощает x ₁x ₂);

г) конъюнктивное склеивание по x ₂:

д) дизъюнктивное склеивание по x ₂:

;

е) конъюнктивное развертывание по x ₂:

;

ж) дизъюнктивное развертывание по x ₂:

.

Основные законы:

а) ассоциативность дизъюнкции и конъюнкции:

,

б) коммутативность дизъюнкции и конъюнкции:

в) дистрибутивность конъюнкции относительно дизъюнкции:

;

г) дистрибутивность дизъюнкции относительно конъюнкции:

.

ВЫЧИСЛЕНИЕ ЛОГИЧЕСКИХ ФУНКЦИЙ

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

Пример 4.
Дана булева функция

Необходимо построить ее таблицу истинности.
Решение.
Функция трех переменных имеет всего восемь значений. Каждое получается на соответствующем наборе, начиная с набора
0,0,0 (x₁ = 0, x₂ = 0, x₃ = 0),
кончая набором
1,1,1 (x₁ = 1, x₂ = 1, x₃ = 1).
При вычислении пользуемся соотношениями:

Результаты сведем в таблицу:

№ набора	x₁	x₂	x₃	f(x₁, x₂, x₃)
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	0
4	1	0	0	1
5	1	0	1	1
6	1	1	0	0
7	1	1	1	0

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

Пример 15.
Дана логическая задача. Алексей, Борис и Валерий нашли в земле сосуд. Рассматривая удивительную находку, они выразили предположения:
Алексей: "Это греческий сосуд и изготовлен в V веке";
Борис: "Это финикийский сосуд и изготовлен в III веке";
Валерий: "Это сосуд не греческий и изготовлен в IV веке".
Впоследствии оказалось, что каждый из них прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?
Решение.
Обозначим символами высказывания:

х₁ - "Найденный сосуд греческий",

х₂ - "Найденный сосуд финикийский",

х₃ - "Сосуд изготовлен в V веке",

х₄ - "Сосуд изготовлен в III веке",

х₅ - "Сосуд изготовлен в IV веке".

Запишем сложные высказывания - предположения школьников:
х₁х₃ - "Сосуд греческий и изготовлен в V веке" (Алексей).
По условию задачи известно, что это высказывание ложно: Алексей прав только в чем-то одном, т.е. х₁=1, х₃=0 или х₁=0, х₃=1. Истинным же будет высказывание:

х₂х₄ - "Сосуд финикийский и изготовлен в III веке" (Борис).
Рассуждая аналогично, получим:

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

Итак, имеем систему уравнений:

Порассуждаем логически. Сосуд может быть изготовлен только в одной стране, то есть x₁ = 0.
Сосуд может быть изготовлен только в одном веке:

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

Таким образом, решить задачу - значит указать, при каких значениях х₁, х₂, х₃, х₄, х₅ сложное высказывание Х истинно.
Найти набор, при котором Х = 1 можно, вычисляя значения Х на всех возможных наборах, заполняя таблицу истинности.

Видно, что набор N=12 единственный, при котором Х=1 . Комбинация истинных высказываний: сосуд финикийский ( х₂=1) и изготовлен в V веке ( х₃=1).

№ набора	х₁х₂х₃х₄х₅
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31	0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1	0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Другой способ решения этой задачи заключается в упрощении функции Х(х₁, х₂, х₃, х₄, х₅) с использованием основных тождеств, правил и законов алгебры логики. Произведем преобразования:

Учитывая, что х₁х₂= 0 и х₃х₄= 0 :

Учитывая, что

, окончательно получим:

Это означает, что Х = 1 только при совпадении: х₁ = 0, х₂ = 1, х₃ = 1, х₄= 0, х₅ = 0, т.е. сосуд - финикийский, изготовлен в V веке.

Пример 16.
Вернувшись домой, Мегрэ позвонил на набережную Орфевр.

Говорит Мегрэ. Есть новости?
Да, шеф. Поступили сообщения от инспекторов. Торранс установил, что если Франсуа был пьян, то либо Этьен убийца, либо Франсуа лжет. Жуссье считает, что Этьен - убийца, или Франсуа не был пьян, и убийство произошло после полуночи. Инспектор Люка просил передать, что если убийство было совершено после полуночи, то либо Этьен убийца, либо Франсуа лжет. Затем звонила : .
Все. Спасибо. Этого достаточно. - Комиссар положил трубку. Он знал, что трезвый Франсуа никогда не лжет. Теперь он знал все.

Какой вывод сделал Мегрэ?
Решение.
Рассмотрим высказывания: х₁ - "Франсуа был пьян", х₂ - "Этьен - убийца", х₃ - "Франсуа лжет", х₄ - "Убийство произошло после полуночи".

Выразим высказывания инспекторов формулами (составные высказывания).
Торранс:

(Импликация - "если : то").
Жуссье:

Люка:

Так как эти высказывания предполагаются истинными, то истинной будет и их конъюнкция F:

Освободимся от импликации с помощью формулы

.
Раскрыв скобки и выполнив несложные преобразования, получим:

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

убийство произошло после полуночи ( х₄).
Так как

("Трезвый Франсуа не лжет"), то

.
Следовательно, истинно х₂, то есть убийца - Этьен.

Blog

Слово "логика" происходит от древнегреческого "логос", имеющего значения: слово, наука, разум

Содержание

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