Лекция "Теоретические основы логики"


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

Логика и алгоритмы

Если теория алгоритма в некотором смысле мать современных ЭВМ и программирования, то логика - их отец.

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

Какое же отношение имеет логика к ЭВМ и КВТ?
  1. Логика является теоретической основой современных ЭВМ, и сложных управляющих систем. Она приобретает важное значение в области специальных языков для баз данных и представлении знаний.
  2. Логика является одной из дисциплин, образующей математический фундамент информатики. Из логических исследований основ математики возникло понятие алгоритма.
  3. В ВТ и автоматике используются логические схемы, устройства, которые преобразуют двоичные сигналы.
  4. Особое значение логическая наука стала приобретать вопрос искусственного интеллекта.

Этапы развития логики

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

Первый этап связан с работами древнегреческого мыслителя Аристотеля (384-322 г. до н.э.). Именно он подверг анализу человеческое мышление. Такие его формы, как понятие, суждение, умозаключение и рассмотрел мышление со стороны структуры, т.е. формально. Так возникла формальная логика,- наука, пытавшаяся найти ответ на вопрос: “Как мы рассуждаем?”, изучающая логические операции и правила мышления.

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

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

Второй этап - появление математической или символической логики. Ее основу заложил немецкий математик и философ - Вильгельм Лейбниц (1646-1716). Это он в XVII веке пытался построить первые логические исчисления и впервые высказал мысль о возможном применении двоичной системы счисления в вычислительной математике, но идее суждено было получить дальнейшее развитие лишь в середине XIX века в трудах другого английского математика - Джорджа Буля. Он вывел для логических построений особую алгебру (алгебру логики). В отличие от обычной, в ней оперируют не числами, а высказываниями.

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

Основные формы абстрактного мышления

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

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

Суждением называется всякое утверждение, о котором можно судить: истинно оно или ложно. (“Москва - столица России”(истина), “сумма улов треугольника равна 90 градусов”(ложь)).

Если из двух суждений выводится третье, то этот процесс называется умозаключением. Пример: Академик Ершов русифицировал язык Паскаль. Язык Паскаль - структурный язык. Умозаключение: Академик Ершов русифицировал структурный язык.

В алгебре логики все высказывания рассматриваются только с точки зрения логического значения, от их житейского содержания отвлекаются. Будем обозначать элементарные суждения заглавными буквами латинского алфавита. Единственно существенной характеристикой алгебры логики является истинность или ложность каждого высказывания. Значение истинности суждения обозначим числом 1 и 0, если значение ложное.

Логическая единица не есть штука чего-то реального, а знак того, что свершилось событие; логический ноль - свершилось ложное событие.

Пример:
A=“Уфа - столица Башкортостана” (истина)
B=“Все горы выше 15 км” (ложь).

Суждения подразделяются на общее частное. Частное суждение выражает конкретные факты. Примеры: “Луна - спутник Земли”, “7-2>3”.

Общее суждение характеризует свойство групп объектов или явления.

Пример: “В любом прямоугольном треугольнике один угол равен 90 градусов”, “Всякий человек- млекопитающий”.

Суждения бывают простыми и сложными. Суждение считается простым, если никакая его часть не является суждением. (“Киев - столица Украины”). Сложное суждение характеризуется тем, что состоит из нескольких суждений, объединенных связками (и, или, не, если то, ...).

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

Примеры: “Если треугольник равносторонний, то все его углы равны между собой”, “Если король под шахом и ему некуда ходить, то мат”.

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

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

Пример: “На Земле есть вода, атмосфера и жизнь” (“На Марсе есть вода и атмосфера, значит на Марсе есть жизнь”.

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

Пример: “Ученик 10”а” Петров опоздал на урок” (“Все ученики 10”а” опоздали на урок”).

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

Пример: “Все рыбы плавают”(“Окунь плавает”).

Алгебра суждений

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

Существуют логические операции:

Отрицание

Отрицанием суждения A называется новое суждение, которое является истинным, если суждение A ложно (и ложно, если суждение A истинно). Эту операцию называют инверсией или логическим “не”.
Обозначения: , не A, not A.

Таблица истинности логического “не”:

0

1

1

0

Конъюнкция

Конъюнкцией двух высказываний A и B называется новое высказывание, которое считается истинным, если A и B истинные, и ложным, если одно из них ложно. Данная операция соответствует союзу ”и”. Обозначения: A^B, A и B, A and B, A&B, A*B.

Таблица истинности логического “и”:

A

B

A*B

0

0

0

0

1

0

1

0

0

1

1

1

Из таблицы видно, что “и” - логическое умножение.
Пример:

A=“Сегодня солнечный день”, B=“Остап пошел купаться”.
A и B (“Сегодня солнечный день и Остап пошел купаться”).

Дизъюнкция

Дизъюнкцией двух высказываний называется новое высказывание, которое считается истинным, если хотя бы одно из них истинно, и ложным, если оба высказывания ложные. Данная операция соответствует союзу ”или”. Обозначение: AÚB, A или B, A or B, A+B. 

Таблица истинности логического “или”:

A

B

A+B

0

0

0

0

1

1

1

0

1

1

1

1

Из таблицы видно, что “или” - логическое сложение.
Пример:

A=“ Днем будет холодно”, B=“ Ночью будет холодно”.
A или B (“Днем или ночью будет холодно”).

При составлении таблиц истинности следует учитывать, что в общем случае количество вариантов перебора равно 2n, где n - количество переменных. Количество строк равно 2n, количество столбцов = количество переменных + количество операций.

Порядок выполнения логических операций

  1. Операции в скобках
  2. Отрицание
  3. Логическое умножение (конъюнкция)
  4. Логическое сложение (дизъюнкция)

Булева алгебра

В 1847 английский математик и преподаватель университета Джордж Буль разработал алгебру логики. Почти 100 лет эта алгебра логики не была известна широкому круги пользователей. Лишь в 1938 году выдающийся американский математик и инженер Клод Шеннон обнаружил, что алгебра логики приложима к любым переменным, которые могут принимать только два значения. В результате алгебра логики явилась математической основой теории электрических и электронных переключательных схем, используемых в ЭВМ.

Законы булевой алгебры

1) A=A

2) A+A=A
A*A=A

3) A*=0

4) +=1

5) A+1=1
A*1=A
A+0=A
A*0=0

6)

7) A+B=B+A
A*B=B*A

8) (A+B)+C=A+(B+C)
(A*B)*C=A*(B*C)

9) A*(B+C)=(A*B)+ (A*C)
A+(B*C)=(A+B)*(A+C)

10)


11) (A+B)*=A*
(A*B)+=A+

12) A*(B+)=A
A+(B*)=A
A*(A+B)=A
A+(A*B)=A

Примеры решения задач

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








Задания для самостоятельной работы

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









Задачи для самостоятельной работы

  • В одном доме живут Воронов, Павлов, Журавлев, Спицын. Один из них – математик, другой – художник, третий – писатель, а четвертый – баянист. Кто из них художник, если известно, что...
  1. ни Воронов, ни Журавлев не умеют играть на баяне
  2. Журавлев не знаком с Вороновым
  3. писатель и художник в воскресенье уезжают на дачу к Павлову
  4. писатель собирается написать очерк о Спицыне и Воронове
  • Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F?

Ответ: 4

  • Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа).
    Какое выражение соответствует F?
Ответ: 3
  • При составлении расписания на вторник учителя высказали свои пожелания по поводу расположения первых пяти уроков. Учитель химии (Х) хочет иметь второй или третий урок, учитель литературы (Л) - первый или второй, учитель информатики (И) - первый или четвертый, учитель технологии (Т) - третий или четвертый, учителя английского языка (А) устраивают только четвертый или пятый уроки.
    Какое расписание устроит всех учителей?
  1. ИЛТХА
  2. ЛХТИА
  3. ЛХИТА
  4. ИХТЛА
  • Для какого слова истинно высказывание:
¬ (Первая буква согласная  → (Вторая буква согласная v Последняя буква гласная))?
  1. ГОРЕ
  2. ПРИВЕТ
  3. КРЕСЛО
  4. ЗАКОН
  • Для какого имени истинно высказывание:
(Первая буква согласная  v  Вторая буква гласная) → В слове 4 буквы?
  1. МИХАИЛ
  2. ГРИГОРИЙ
  3. ЕВГЕНИЙ
  4. ИОЛАНТА

  • На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Ответ: 12

Comments