АЛГЕБРА ВЫСКАЗЫВАНИЙ

1. Задания для творческого (поискового) уровня.

Составьте перечень нормативных источников к данной теме, используйте справочно-правовые системы «Гарант» и «Юрист».

1.Глава XVII. Международно-правовой механизм охраны окружающей среды

2. Постановление Правительства РФ от 30 сентября 2008 г. N 731 "О внесении изменений в постановление Правительства Российской Федерации от 10 августа 1998 г. N 919"   Подпрограмма явилась системным механизмом для реализации действий, связанных с международно-правовым статусом Антарктики. Россия как участница международного Договора об Антарктике 1959 года взяла на себя определенные обязательства, в том числе:

3.Постановление Правительства РФ от 10 августа 1998 г. N 919 "О федеральной целевой программе "Мировой океан" (с изменениями и дополнениями)   Подпрограмма явилась системным механизмом для реализации действий, связанных с международно-правовым статусом Антарктики. Россия как участница международного Договора об Антарктике 1959 года взяла на себя определенные обязательства, в том числе:

4.Слепенкова О.А., Агешкина Н.А. Комментарий к Федеральному закону от 19 июля 1997 г. N 109-ФЗ "О безопасном обращении с пестицидами и агрохимикатами". - Специально для системы ГАРАНТ, 2012 г.

5.Предмет, система и принципы международного права окружающей среды (О.И. Тиунов, "Журнал российского права", N 6, июнь 2013 г.)

6.Роль международно-правовых стандартов в регулировании взаимодействия международного и национального права (О.И. Тиунов, "Журнал российского права", N 12, декабрь 2012 г.)

 

АЛГЕБРА ВЫСКАЗЫВАНИЙ

 

План:

1. Предмет матлогики

2. Высказывания

3. Понятие формулы, подформулы

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

5. Логические операции бинарной логики

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

7. Порядок упрощения формулы

 

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

 

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

 

Основная идея математической логики – формализация знаний и рассуждений. Предмет исследования матлогики – это математическое доказательство. Доказательство рассуждения – единственный вид признаваемых в матлогике рассуждений. Рассуждения в матлогике изучаются с точки зрения формы, а не смысла. Процесс моделирования рассуждений называют выводом. Матлогика оперирует только синтаксическими понятиями.

 

Создателем формальной логики является Аристотель. Формальная логика изучает суждения, умозаключения, доказательства с точки зрения их формы, структуры, абстрагируясь от конкретного содержания. Задача логического исследования – обнаружение и систематизация определённых схем правильного рассуждения.

 

Первую завершённую систему матлогики – алгебру логики – предложил Джордж Буль (1815 – 1864). Большой вклад внёс Г. Фреге (1848 – 1925), ввёл понятие предикату и кванторов. Изложение целых разделов математики на языке матлогики и аксиоматизации арифметики выполнены Джузеппе Пеано (1858 – 1932).

 

Учёные Г. Фреге и Б. Рассел сделали попытку свести всю существующую математику к логике, однако эта работа потерпела крах. Логицизм оказался утопией.

 

Применение матлогики:

1. Является основой математических рассуждений

2. Используется в информатики – в работе алгоритмов вычислительных систем

3. В науке и технике – в системах принятия решений

 

Простейший пример применения матлогики:

Задача: в соревнованиях по гимнастике на первенство школы участвуют Алла, Валя, Таня и Даша. Болельщики высказали предположения о возможных победителях:

1. Первой будет Таня, Валя будет второй

2. Второй будет Таня, Даша – третьей

3. Алла будет второй, Даша – четвёртой.

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

 

Высказывание – повествовательное предложение, относительно которого имеет смысл говорить, что его содержание истинно или ложно. Принято обозначать латинскими буквами, например, A, B, C. Истинные высказывания обозначаются И или 1, ложные – Л или 0.

 

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

 

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

 

Троичная логика (трёхзначная логика) – один из видов многозначной логики, предложенный Ямом Лукасевичем в 1920-м году. Трёхзначная логика является исторически первой многозначной логикой, простейшим расширением двузначной логики. Кроме “истинно” и ”ложно” трёхзначная логика включают третье значение, которое трактуется “не определено” или “неизветсно”.

 

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

 

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

 

1.

(т. е. при , при и при ).

 

2.

Т. е. значение истинности импликации высказываний и равно меньшему из чисел 1 и , например, при и импликациия имеет значение .

 

Таблица истинности для операции трёхзначной логики:

 

Для :

½	½

 

 

Для :

 

		½
		½
½			½

 

 

Стандартно используется двоичная логика.

 

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

 

Итак, пусть определены следующие операции:

´ Отрицание (унарная операция)

´ Конъюнкция (бинарная)

´ Дизъюнкция (бинарная),

 

а также константы – логический ноль 0 и логическая единица 1. Далее выбирается система аксиом. Системы аксиом могут различаться числом аксиом. Минимальная содержит 3, максимальная – обычно 12.

 

Пример системы аксиом:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

 

Матлогика делится на классическую и на неклассическую. Классическая – бинарная логика, основанная на принятой системе аксиоматик, но аксиоматики могут быть различными, в конечном итоге сводятся одна к другой, традиционное представление операций (например, импликации). Неклассическая логика (возникла позже, но имеет широкое применение) – или не бинарная логика, или традиционное понимание логический операций, например импликации.

 

В нечёткой логике, в отличие от классической, вместо величин “истина” и “ложь” используется величина “степень истинности”, принимающая любые значения из бесконечного множества от 0 до 1 включительно. Следовательно логические операции уже нельзя представить таблично. В нечёткой логике они задаются функциями.

 

Есть два способа реализации дизъюнкции и конъюнкции:

 

Максиминный подход:

 

Колориметрический подход:

 

Отрицание задаётся единственным способом:

 

Вернёмся к классической логике.

 

Конъюнкция (conjunction – включение) – логическая операция, по своему применению максимально приближена к союзу “и”. Логическое “и” или логическое умножение. Минимальное значение аргументов. Имеет место и A, и B.

 

Таблица истинности для бинарной конъюнкции:

 

 

 

Свойства конъюнкции:

1.

2.

3.

 

Таблица истинности для свойств конъюнкции:

 

 

 

Дизъюнкция (disjunction – разобщение) – логическая операция, по своему применению максимально приближена к союзу “или”. Логическое “или”, включающее “или”, логическое сложение. Имеет место либо A, либо B.

 

Таблица истинности для бинарной дизъюнкции:

 

 

 

Отрицание – унарная операция над высказываниями, результатом которой является суждение, в известном смысле “противоположное” исходному. Обозначается чертой над обозначением высказывания. В классической логике имеет место закон двойного отрицания. Двойное отрицание высказывание означает само высказывания.

 

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

 

Эквивалентность (равносильность) – “тогда и только тогда, когда...”, “если и только если...”. Обозначается знаком Отметим, что формула эквивалентна форуле .

 

Таблица истинности для эквивалентности:

 

<вставить таблицу дома>

 

Лукасевич предложил систему аксиом, которые выражены только через операции импликации и отрицания:

 

1.

2.

3.

 

Через эти же операции к системе аксиом присоединяются определения конъюнкции, дизъюнкции и эквивалентности.

 

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

1. Если – пропозициональная переменная, то – формула

2. Если – формула, то – формула

3. Если и – формулы, то , и – формулы

4. Других соглашений нет.

 

Всякая пропозициональная переменная является формулой.

 

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

1.

2.

3.

 

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

 

Запишем, что ни одно из мест не было разделено участниками:

 

или

ИЛИ

или

 

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

 

или

или

 

 

Задание: формализовать следующее условие.

На ледяном поле 5 хоккеистов – Ольховский, Малышев, Белов, Таманин, Лавров – штурмовали ворота. Раздался свисток судьи. “Удаляет всех” – подумали спортсмены. “Без Малышева или Ольховского я не останусь на поле” – сказал Таманин. “Я тоже” – сказал Лавров. “Удаляют либо меня с Беловым, либо Таманина с Лавровым” – сказал Малышев. Когда судья объявил о своём решении, все оказались правы и, кроме того, Ольховский и Белов не остались вместе на поле. Кто остался на поле?

 

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

 

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

 

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

 

Две формулы алгебры логики и называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в формулы элементарных высказываний. Равносильность формул обозначается знаком “ ”. Запись означает, что формулы и равносильны.

 

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

 

Важнейшие равносильности алгебры логики принято разбивать на три группы.

 

Первая группа – основные равносильности.

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

Третья группа – основные законы алгебры логики.

 

 

1. Основные равносильности:

 

· ,

·

·

·

·

· – закон противоречия

· – закон исключённого третьего

· – закон снятия двойного отрицания

· , – законы поглощения

 

 

2. Равносильности, выражающие одни операции через другие:

 

·

·

·

·

·

·

 

 

3. Равносильности, выражающие основные законы алгебры логики:

 

· – коммутативность дизъюнкции

· – коммутативность конъюнкции

· – ассоциативность конъюнкции

· – ассоциативность дизъюнкции

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

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

 

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

 

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