Решение

.

Подставим , получим ; , получим .

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

Пример 3. Отображение действует по правилу

. Найдите образ .

Решение

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

 

 

Вопросы и задачи для самостоятельного решения

1. Дайте определения образа, прообраза функции.

2. Найдите прообраз множества при отображении .

3. Отображение действует по правилу

. Найдите образ .

4. Найдите области определения следующих функций:

а) ; б) .

2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

2.1. Математическая логика как наука

Как самостоятельная наука логика оформилась в трудах греческого философа Аристотеля (384–322 гг. до н.э.). Он систематизировал известные до него сведения, и эта система стала впоследствии называться формальной, или аристотелевой, логикой. Формальная логика просуществовала без серьезных изменений более двадцати столетий. Сочинение Аристотеля «Аналитики» долгое время рассматривали как труд, завершающий развитие этой науки. Исследования математики выявили недостаточность аристотелевой логики и потребовали дальнейшего ее развития.

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

Впервые в истории идеи о построении логики на математической основе были высказаны немецким математиком Г. Лейбницем (1646–1716) в конце XVII в. Он считал, что основные понятия логики должны быть обозначены символами, которые соединяются по особым правилам.

Первая реализация идеи Г. Лейбница принадлежит английскому ученому Дж. Булю (1815–1864). Он создал алгебру, в которой буквами обозначались высказывания, что привело к появлению алгебры высказываний. Именно благодаря введению символов в логику была получена основа для создания новой науки – математической логики. Джордж Буль развил алгебраический подход к логике и сформулировал правила логических вычислений. В труде «Исследование законов мышления» он использовал алгебраическую символику для логических операций. Так, операция отрицания переменной вычислялась как разность , дизъюнкция (логическое сложение) переменных и – как выражение и т. д.

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

К концу XIX столетия актуальное значение для математики приобрели вопросы обоснования ее понятий и идей. Эти задачи имели логическую природу и, естественно, привели к дальнейшему развитию математической логики. В этом отношении показательны работы немецкого математика
Г. Пеано (1858–1925), который применил математическую логику для обоснования арифметики и теории множеств.

Математическая (формальная) логика делится на три подраздела: логику Буля, логику высказываний и логику предикатов.

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

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

 

2.2. Высказывания. Логические операции и их основные свойства

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

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

Например, «Москва – столица России», «число 2 больше 5» – высказывания. Первое высказывание является истинным, а второе – ложным.

Будем обозначать высказывания латинскими буквами:

 

Логическое значение высказывания «истина» обозначается цифрой «1», «ложь» – «0».

Предложения: «Который час?», «ответьте на вопрос», «добро пожаловать!» – не являются высказываниями.

Предложение «Была метель» также не является высказыванием, пос­кольку нет достаточной информации, чтобы установить истинно оно или ложно (где и когда?).

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

Определение 4.Если суждение об истинности высказывания можно вынести из самого высказывания, то такое высказывание называют простым. В противном случае мы имеем сложное (составное) высказывание.

Значение истинности составного высказывания определяется значениями истинности его компонент.

Из простых высказываний можно образовать новые составные высказывания с помощью союзов «и», «или», «либо», «если…, то», «тогда и только тогда, когда», «неверно, что». Эти союзы называются логическими связками. Построение из данных высказываний нового составного высказывания называется логической операцией над высказываниями.

Основные логические операции: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность (табл. 1).

Таблица 1

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

Название	Прочтение	Обозначение
Отрицание	Не; неверно, что	( )
Конъюнкция	И; а	( )
Дизъюнкция	Или
Импликация	Если … то
Эквивалентность	Тогда и только тогда, когда	(~)

 

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

Пусть даны два произвольных высказывания и .

Определение 5.Отрицаниемвысказывания называется высказывание («не », «неверно, что »), которое истинно, когда ложно, и ложно, когда истинно.

Таблица истинности для отрицания:

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

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

 

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

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

 

 

Определение 8.Импликацией двух высказываний , называется высказывание («если , то », « влечёт », «из следует », « имплицирует »), которое ложно тогда и только тогда, когда истинно, а ложно.

Таблица истинности для импликаций:

 

Определение 9.Эквивалентностью высказываний , называется высказывание (« эквивалентно », « тогда и только тогда, когда », «для того, чтобы , необходимо и достаточно, чтобы »), которое истинно тогда и только тогда, когда и оба истинны или ложны.

 

 

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

 

 

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

Например, составными будут высказывания: ; ; .

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

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

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

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

Пример 1. Составьте таблицу истинности .

Решение

Составим таблицу истинности, последовательно выполняя логические операции, входящие в формулу:

 

 

 

Пример 2. Пусть , и обозначают соответственно высказывания: «Тимофей любит шахматы», «Тимофей любит футбол», «Тимофей любит баскетбол». Требуется записать высказывание: «Тимофей любит шахматы и неверно, что он любит футбол или баскетбол» в символической форме и указать соответствующую таблицу истинности.

Решение

Высказывание «Тимофей любит футбол или баскетбол» в символичес­кой форме записывается как . Высказывание «Неверно, что Тимофей любит футбол или баскетбол» символически записывается как , пос­кольку отрицание применяется ко всему высказыванию.

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

Таблица истинности этого высказывания:

 

Пример 3. Запишите высказывание «Если число 72 делится на 6, а число 6 делится на 2, то число 72 делится на 2» в символической форме.

Решение

Выделим простые высказывания «число 72 делится на 6», «число 6 делится на 2», «число 72 делится на 2» и заменим их логическими переменными , и соответственно.

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

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

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

Например, , – равносильные формулы:

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

 

 

Определение 13.Формула называется тавтологией или тождественно истинной, если она принимает значение «истина» при всех значениях входящих в неё переменных.

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

Теорема. тогда и только тогда, когда .

Каждое высказывание вида – тавтология.

Определение 14.Логическая формула называется тождественно ложной, или противоречием (записывается ), если для всех наборов значений входящих в нее переменных (высказываний) она принимает значение 0 («ложь»), т. е. если высказывание ложно в каждом случае.

Таблица истинности для противоречия содержит только значения 0 в итоговом столбце.

Заметим, что отрицание любой тавтологии есть противоречие: .

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

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

Основные равносильности алгебры высказываний:

1) – ассоциативность операций и ;

2) – коммутативность операций и ;

3) – закон идемпотентности;

4) – законы дистрибутивности;

5) – законы поглощения;

6) – законы склеивания;

7) – законы Порецкого;

8) – законы де Моргана;

9) ;

10) ;

11) ;

12)

13) –закон двойного отрицания;

14) –закон исключения третьего;

15) – закон противоречия;

16) – закон контрапозиции.

Пример 4. Докажите равносильность с помощью формул алгебры высказываний:

а) ;

б) .

Решение:

a) используя формулу , запишем: , тогда по закону де Моргана и по закону двойного отрицания получим , что и требовалось доказать;

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

Левая часть: .

Правая часть:

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

Вопросы и задачи для самостоятельного решения

1. Определите, какие из следующих предложений являются высказываниями:

а) «ученики школы»;

б) «7 + 5 = 12»;

в) «сегодня плохая погода»;

г) «если , то »;

д) «у каждого человека есть домашнее животное»;

е) «для всех действительных чисел и верно равенство »;

ж) «треугольник равен треугольнику »;

и) «берегись автомобиля!».

2. Составьте таблицы истинности для логических формул:

а) ; г) ;

б) ; д) .

в) .

3. Запишите следующие высказывания в символической форме и укажите соответствующую таблицу истинности:

а) «неверно, что ни Евгений, ни Николай не умеют играть на гитаре»;

б) «если числовая последовательность монотонна и ограничена, то она имеет предел»;

в) «неверно, что если белый кубик больше зеленого, а зеленый – больше синего, то синий кубик больше белого».

4. Проверьте с помощью таблицы истинности, будут ли эквивалентны следующие логические формулы:

а) ;

б) ;

в) .

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

а) ; б) ; в) ;

; ; .

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

Таблица истинности штриха Шеффера:

 

 

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

Штрих Шеффера , или антиконъюнкция, по определению (читается « несовместимо с »).

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

Таблица 2

Новые логические операции

Название	Прочтение	Обозначение
Штрих Шеффера	Антиконъюнкция
Стрелка Пирса (штрих Лукасевича)	Антидизъюнкция
Сумма по модулю два (сумма Жегалкина)	Антиэквивалентность

 

Стрелка Пирса , или антидизъюнкция, по определению (читается «ни , ни »).

Таблица истинности стрелки Пирса:

 

 

Сумма по модулю два , или антиэквивалентность, по определению .

Таблица истинности суммы по модулю два:

 

 

В формулах действует следующий порядок старшинства операций: отрицание «–» (если оно относится к одному высказыванию, например ), штрих Шеффера « », стрелка Пирса « », конъюнкция « », дизъюнкция « », сумма по модулю два « », импликация « », эквивалентность « ».

Вопросы и задачи для самостоятельного решения

1. Составьте таблицы истинности для логических формул:

а) ;

б) ;

в) .

2. Проверьте с помощью таблицы истинности, будут ли эквивалентны следующие логические формулы:

а) ;

б) ;

в) .

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

а) ; б) ; в) ;

; ; .

 

2.3. Способы решения логических задач

2.3.1. Решение логических задач средствами алгебры логики

Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа решения логических задач:

§ средствами алгебры логики;

§ табличный;

§ с помощью рассуждений.

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

1) изучается условие задачи;

2) вводится система обозначений для логических высказываний;

3) конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

4) определяются значения истинности этой логической формулы;

5) из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

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

Инструкция по выявлению неисправных узлов такова:

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

2) если неисправен узел , но исправен узел , то загорается лампочка ;

3) если неисправен узел , но исправен узел , загорается лампочка , но не загорается лампочка ;

4) если неисправен узел , но исправен узел , то загораются лампочки и или не загорается лампочка ;

5) если горит лампочка и при этом либо неисправен узел , либо все три узла , , исправны, то горит и лампочка .

В пути компьютер сломался. На контрольной панели загорелась лампочка . Тщательно изучив инструкцию, путешественник починил компьютер. Но с этого момента и до конца плавания его не оставляла тревога. Он понял, что инструкция несовершенна, и есть случаи, когда она ему не поможет. Какие узлы заменил путешественник?

Решение

Введем обозначения для логических высказываний:

– неисправен узел ;

– неисправен узел ;

– неисправен узел ;

– горит лампочка ;

– горит лампочка ;

– горит лампочка .

Правила 1–5 выражаются следующими формулами:

(1) ;

(2) ;

(3) ;

(4) ;

(5) .

Формулы (1)–(5) истинны по условию, следовательно, их конъюнкция тоже истинна:

 

Выражая импликацию через дизъюнкцию и отрицание по формуле , получаем:

 

 

 

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

 

 

Отсюда следует, что , , .

Ответ: нужно заменить блоки и ; блок не требует замены.

Пример 2.На вопрос, какая завтра погода, синоптик ответил: если не будет ветра, то будет пасмурная погода без дождя; если будет дождь, то будет пасмурно и без ветра; если будет пасмурно, то будет дождь и не будет ветра. Какая завтра будет погода?