Задание 2 (Задание В4 демоверсии 2008г)

Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров:

A) Макс победит, Билл – второй;

B) Билл – третий. Ник – первый;

C) Макс – последний, а первый – Джон.

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

Какое место на турнире заняли Джон, Ник, Билл, Макс?

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

Оценки за урок.

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

Для преобразования логических формул к равносильным используются законы алгебры логики:

1. законы коммутативности
   • x ∧ y = y ∧ x
   • x ∨ y = y ∨ x
2. законы ассоциативности
   • (x ∧ y) ∧ z = x ∧ (y ∧ z)
3. (x ∨ y) ∨ z = x ∨ (y ∨ z)
4. законы поглощения (нуля и единицы)
5. законы дистрибутивности
   • x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)
   • x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)
6. закон противоречия
7. закон исключенного третьего
8. законы идемпотентности
9. закон двойного отрицания
10. законы де Моргана
    • ¬ (x ∧ y) = ¬ x ∨ ¬ y
    • ¬ (x ∨ y) = ¬ x ∧ ¬ y
11. законы поглощения
12. x ∧ (x ∨ y) = x

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

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

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

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

1) Для доказательства раскроем скобки в правой части закона:
  (x + y) • (x + z) = x • x + x • z + y • x + y • z
2) Используем закон идемпотентности: x • x = x. В результате имеем,
  x + x • z + y • x + y • z
3) Применим закон поглощения x + x • z = x. После преобразования получим,
  x + y • x + y • z
4) Применим закон поглощения x + y • x = x. Окончательно получаем,
  x + y • z
Таким образом, (x + y) • (x + z) = x + y • z
Равенство доказано.

Логическое следование — Гуманитарный портал

Логические выражения | Кабинет информатики

Понятие логического выражения или логической формулы вводится индуктивно.

Логической формулой является

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

2) если A и B — формулы, то, А*В и (А*В) — тоже формулы, где знак “*” означает любую из логических бинарных операций (см. “Логические операции. Кванторы”).

Формулой является, например, следующее выражение (x & y) z. Каждой формуле при заданных значениях входящих в нее переменных можно приписать одно из двух значений — 0 или 1.

Формулы А и В, зависящие от одного и того же списка переменных x1, x2, x3, …, xn, называют равносильными, или эквивалентными, если на любом наборе значений переменных x1, x2, x3, …, xn они принимают одинаковые значения. Для обозначения равносильности формул используется знак равенства, например, А = В.

Любую формулу можно преобразовать к равносильной ей, в которой используются только операции &, и отрицание.

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

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

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

Для логических операций в одном логическом выражении установлен следующий порядок вычислений:

· отрицание — первый, наивысший приоритет;

· конъюнкция — второй приоритет;

· дизъюнкция, разделительная дизъюнкция — третий приоритет;

· импликация, эквивалентность — низший приоритет.

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

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

Канонические формы

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

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

Формулу называют элементарной конъюнкцией, если она является конъюнкцией одной или нескольких переменных, взятых с отрицанием или без отрицания. Например, формулы x₂, x₂, x₁ & x₃, x₁ & x₃ & x₁ & x₃  являются элементарными конъюнкциями.

Формула называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией элементарных конъюнкций. ДНФ записываются в виде A₁ A₂ … A_n, где каждое A_i — элементарная конъюнкция. Например, x₂x₁ & x₃, x₂ & x₂x₁ & x₂— дизъюнктивные нормальные формы.

Формула А от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если

1) А является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных x₁, x₂, …, x_k, причем на i-м месте этой конъюнкции стоит либо переменная x_i, либо ее отрицание;

2) все элементарные конъюнкции в такой ДНФ попарно различны.

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

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

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

Теорема. Пусть — f (x₁, x₂, …, x_n)булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию f, которую можно построить по следующему алгоритму:

1. В таблице истинности отмечаем наборы переменных, на которых значение функции f равно единице.

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

3. Все полученные конъюнкции связываем операциями дизъюнкции.

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

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

Доказательство. Для всех функций, отличных от 0, это можно сделать с помощью СДНФ, а ноль можно выразить, например, как x &`x.

Методические рекомендации

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

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

2) Во многих языках программирования используется только несколько логических операций, как правило, операция логического сложения, логического умножения и отрицания, а также операция разделительной дизъюнкции. Поэтому, если полученная формула содержит не только операции &, и отрицание, то учащиеся должны уметь выполнять тождественные преобразования для построения ДНФ (дизъюнктивной нормальной формы). Умение выполнять тождественные преобразования основано на знании основных законов алгебры логики, но формируется это умение в результате выполнения большого числа заданий. На формирование этого умения времени практически не отводится, но практика показывает, что достаточно научить учащихся выражать операции импликации и эквивалентности через &, и отрицание. Большинство законов алгебры логики ученикам интуитивно понятны и не требуют запоминания. Исключение составляют законы поглощения и де Моргана. Последние особенно часто применяются в программировании. Знакомство с законами алгебры логики начинается в базовом курсе информатики и продолжается в старшей школе.

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

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

5) Если вы задаете своим ученикам задания на построение отрицания к сложному высказыванию (а проще всего это делать через построение отрицания к соответствующему логическому выражению), то им следует пояснить, почему в этом случае квантор общности заменяется на квантор существования и наоборот (см. “Логические операции. Кванторы”).

Очевидно, что высказывание, содержащее квантор общности (например, “Все мужчины старше 70 лет имеют длинную седую бороду”), можно заменить на следующее: “И Иванов А.П., и Кравцов И.Г., и Петухов С.П., и … старше 70 лет и имеют длинную седую бороду”. Это высказывание можно записать следующей формулой: И & К & П & …, где буквой И обозначено высказывание “Иванов А.П. (который старше 70 лет) носит длинную седую бороду”, буквой К обозначено высказывание “Кравцов И.Г. носит длинную седую бороду” и т.д. При построении отрицания к первоначальному сложному высказыванию, содержащему квантор общности, воспользуемся законом де Моргана. Тогда получим:

Этой формуле соответствует высказывание “Или Иванов А.П. не имеет длинной седой бороды, или Кравцов И.Г. не имеет длинной седой бороды, или Петухов С.П. … или … не имеет длинной седой бороды”, другими словами, “Существует мужчина старше 70 лет, который не имеет длинной седой бороды”.

⁶ От латинских слов idem — тот же самый и potens — сильный; дословно — равносильный.

Импликация и эквивалентность | Практическая информатика

Известно, что любая логическая формула может быть выражена через три ранее рассмотренные логические операции, однако на практике часто используют еще две логические связки. Первая из них называется импликацией и служит для задания так называемых условных высказываний. В русском языке этой логической операции соответствуют фразы если …, то … или когда …, тогда … Импликация — двухместная операция: часть формулы до импликации называют основанием условного высказывания, а часть, расположенную за ней — следствием. В логических формулах импликация обозначается знаком ->. Операция A -> B определяет логическую функцию, тождественно совпадающую с функцией !A || B.

Пример

Дано сложное высказывание: «Если выглянет солнце, то станет тепло». Требуется записать его в виде логической формулы.

Обозначим через А простое высказывание «выглянет солнце», а через В — «станет тепло». Тогда логической формулой этого сложного высказывания будет импликация: A -> B.

Другой распространенной операцией является эквивалентность. Ее аналог в разговорной речи — фразы, подобные словосочетанию тогда и только тогда, когда … или если и только если … Для ее обозначения используется символ <-> или просто =. Мы будем использовать для обозначения эквивалентности обе эти формы. Отметим, что логическая формула A <-> B эквивалентна формуле (A -> B) && (B -> A).

Пример

Дано сложное высказывание: «В зачетную книжку выставляется оценка за экзамен тогда и только тогда, когда он сдан». Нужно преобразовать высказывание к логической формуле. Обозначим через А простое высказывание «В зачетную книжку выставляется оценка за экзамен», а через В  — «Экзамен сдан». Тогда логическая формула сложного высказывания запишется в виде A <-> B.

Приведем таблицу истинности, задающую операции импликации и эквивалентности:

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

Элективный курс по информатике по теме «Математическая логика и теория алгоритмов» — Факультативы, элективы, кружки — Информатика

Одна из задач профильной школы — содействовать воспитанию нового поколения, отвечающего по своему уровню развития и образу жизни условиям информационного общества. Данный элективный курс актуален т.к. он выполняет основные задачи профильной школы.
Эта программа предназначена для проведения элективных курсов по информатике с учащимися 10-11 классов технологического профиля общеобразовательных школ.
Программа составлена на основе федерального компонента государственного стандарта и примерной программы основного общего образования. Программа определяет содержание элективного курса, дает распределение учебных часов по темам курса и определяет последовательность изучения тем.
Занятия проводятся в виде 1 часа в неделю, курс рассчитан на 38 часов. Итоговый контроль проходит на заключительных двух уроках курса в виде тестирования и контрольной работы.
Цель: Формирование представлений о математической логике и теории алгоритмов.
Задачи курса:
• Сформировать логическое мышление учащихся.
• Уметь решать задачи математической логики и теории алгоритмов.
• Применять полученные знания в других разделах информатики (программировании).

Тематическое планирование

№ Название раздела Количество часов Форма проведения Образовательный продукт
Всего Лекции Практика
1

Элементы логики высказываний.
8 5 3 Лекции, работа в группах, индивидуальная работа. Конспект, выполненные задания, таблицы.
2
Логика предикатов. 10 7 3 Лекции, практикум Выполненные задания, конспект, схемы.
3

Математические доказательства. 8 4 4 Лекции, практикум Выполненные задания, конспект, таблица.
4

Теория Алгоритмов
10 5 5 Лекции, практикум Выполненные задания, конспект, таблица.
5 Зачет
2 1 1 Тестирование,
контрольная работа Контрольная работа, тест.
Всего: 38 22 16

Содержание разделов.

РАЗДЕЛ I. Элементы логики высказываний.
Высказывания, их истинностные значения. Логические операции над высказываниями: отрицание, конъюнкция, дизъюнкция, эквиваленция. Таблицы истинности.
Логическая структура составных высказываний. Формулы логики высказываний; таблицы истинности для формул. Равносильность формул. Законы логики. Проверка равносильности с помощью таблиц истинности. Преобразование формул.
Алгебра множеств. Функции алгебры логики. Нормальные формы формул. Логический анализ предложений математического и естественного языков. Проблема разрешимости в алгебре логики.
Исчисление высказываний. Алфавит, формулы исчисления высказываний и правила вывода.
Решение задач средствами логики высказываний.
Учащиеся должны знать:
• этапы составления таблиц истинности;
• основные базовые элементы логических схем;
• правила составления логических схем;
• правила преобразования логических выражений и законы.
Учащиеся должны уметь:
• составлять таблицы истинности;
• решать логические задачи, сформулированные на обычном языке
• составлять логические схемы.

РАЗДЕЛ II. Логика предикатов.
Понятие предиката, предикаты различной местности. Множество истинности предиката. Логические операции над предикатами. Кванторные операции над предикатами.
Формулы логики предикатов. Нормальные формы формулы логики предикатов. Общезначимость и выполнимость формул логики предикатов.
Символическая запись предложений математического и естественного языков; их преобразование; построение отрицаний.
Учащиеся должны знать:
• Понятие предиката, предикаты различной местности;
• формулы логики предикатов;
• множество истинности предиката.
Учащиеся должны уметь:
• выполнять логические операции над предикатами;
• выполнять квантовые операции над предикатами;

РАЗДЕЛ III. Математические доказательства.
Общий вид условного математического предложения, его составные части: разъяснительная часть, условие, заключение. Отношения следования и равносильности между предложениями. Структура теоремы. Виды теорем. Необходимые и достаточные условия. Умозаключения и их виды. Способы математического доказательства.
Учащиеся должны знать:
• общий вид условного математического предложения, его составные части;
• структуру теоремы;
• виды теорем.
Учащиеся должны уметь:
• доказывать математически.
РАЗДЕЛ IV. Теория Алгоритмов
Понятие алгоритма, свойства алгоритма. Понятие эффективно вычисляемой функции (Черч, Гедель). Машина Тьюринга. Структура Машины Тьюринга. Нормальные алгоритмы Маркова. Решение задач с использованием Машины Тьюринга и Нормальных алгоритмов Маркова.
Учащиеся должны знать:
• Понятие алгоритма, свойства алгоритма;
• Структура Машины Тьюринга;
• Нормальные алгоритмы Маркова.
Учащиеся должны уметь:
• Решать задачи с помощью Машины Тьюринга и Нормального алгоритма Маркова.

Литература
1. Булос Дж., Джеффри Р. Вычислимость и логика. М.: Мир, 1994. [С. 12-55, 131-152, 167-180, 253-274.]
2. Мендельсон Э. Введение в математическую логику. М.: Наука, 1984. [С. 19-81, 86-102.]
3. Лавров И. А, Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физ.-мат. литература, 1995. [С. 50-107, 124-147.]
5. Столл Р. Множества, логика, аксиоматические теории. М.: Просвещение, 1968. [С. 72-191.]
6. Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. М.: МГУ, 1991 [С. 17-90, 96-98, 103-133.]
Дополнительная литература
1. Справочная книга по математической логике / Под ред. Дж. Барвайза. Часть 1, Теория моделей. М.: Наука, 1982. [С. 13-55.]
2. Гейтинг А. Интуиционизм. М., Мир, 1965.
3. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.: Мир, 1983. [С. 9-33, 75-114.]
4. Клини С. К. Математическая логика. М.: Мир, 1973. [С. 11-176, 270-296.]
5. Линдон Р. Заметки по логике. М.: Мир, 1968. [С. 11-88.]
6. Успенский В. А. Лекции о вычислимых функциях. М., Физматгиз, 1960. [С. 24-32, 53-81.]
7. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. [С. 11-52.]
8. Фейс Р. Модальная логика. М.: Наука
9. Методическая газета для учителей информатики «1 сентября. Информатика»

Автор: Костюченко Наталья Владимировна, учитель информатики и математики МОУ «СОШ №5» г. Ачинска

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

Есть мнение?
Оставьте комментарий

Как Аристотель создал компьютер

ИСТОРИЯ Компьютеров часто рассказывают как историю объектов, от счетчиков до машины Бэббиджа и машин для взлома кодов времен Второй мировой войны. Фактически, это лучше понимать как историю идей, в основном идей, которые возникли из математической логики, малоизвестной и культовой дисциплины, которая впервые возникла в 19 веке. Пионерами математической логики стали философы-математики, в первую очередь Джордж Буль и Готлоб Фреге, которые сами были вдохновлены мечтой Лейбница об универсальном «языке понятий» и древней логической системой Аристотеля.

Математическая логика изначально считалась безнадежно абстрактным предметом, не имеющим мыслимых приложений. Как прокомментировал один компьютерный ученый: «Если бы в 1901 году талантливому и отзывчивому стороннему наблюдателю пришлось бы исследовать науку и назвать отрасль, которая была бы наименее плодотворной в [] столетие вперед, его выбор вполне мог бы остановиться на математической логике. .И тем не менее, это обеспечит основу для области, которая окажет большее влияние на современный мир, чем любая другая.

Развитие информатики из математической логики завершилось в 1930-х годах двумя знаковыми статьями: «Символьный анализ коммутационных и релейных схем» Клода Шеннона и «О вычислимых числах в приложении к проблеме Entscheidungsproblem » Алана Тьюринга. ” В истории информатики Шеннон и Тьюринг — выдающиеся личности, но важность предшествовавших им философов и логиков часто упускается из виду.

В хорошо известной истории компьютерных наук статья Шеннона описывается как «возможно, самая важная, а также самая известная магистерская диссертация века». Шеннон написал ее, будучи студентом-электротехником в Массачусетском технологическом институте. Его советник Ванневар Буш построил прототип компьютера, известного как дифференциальный анализатор, который мог быстро вычислять дифференциальные уравнения. Устройство было в основном механическим, с подсистемами, управляемыми электрическими реле, которые были организованы специальным образом, поскольку еще не существовало систематической теории, лежащей в основе проектирования схем.Тема диссертации Шеннона возникла, когда Буш порекомендовал ему попытаться открыть такую ​​теорию.

Статья Шеннона во многом является типичной статьей по электротехнике, наполненной уравнениями и диаграммами электрических цепей. Что необычно, так это то, что в первую очередь упоминалась работа по математической философии 90-летней давности — «Законы мышления » Джорджа Буля «».

Сегодня имя Буля хорошо известно компьютерным специалистам (многие языки программирования имеют базовый тип данных, называемый Boolean), но в 1938 году его редко читали за пределами философских факультетов.Сам Шеннон познакомился с работами Буля на студенческом курсе философии. «Просто так получилось, что никто другой не был знаком с обоими месторождениями одновременно», — комментировал он позже.

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

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

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

Действительно, в своей древней схоластической форме предмет логики почти исключительно связан с великим именем Аристотеля. . Поскольку он был представлен Древней Греции в частично технических, частично метафизических исследованиях T и Органон , то без каких-либо существенных изменений он сохранился до наших дней.

Попытка улучшить логическую работу Аристотеля была интеллектуально смелым шагом. Логика Аристотеля, представленная в его книге из шести частей Органон , занимала центральное место в научном каноне более 2000 лет. Было широко распространено мнение, что Аристотель написал почти все, что можно было сказать по этой теме. Великий философ Иммануил Кант заметил, что, начиная с Аристотеля, логика «не могла сделать ни единого шага вперед и поэтому, по всей видимости, кажется законченной и законченной.

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

• Все люди смертны.
• Сократ — мужчина.
• Следовательно, Сократ смертен.

Вы можете заменить «Сократ» любым другим объектом, а «смертный» — любым другим предикатом, и аргумент останется в силе. Достоверность аргумента определяется исключительно логической структурой.Логические слова — «все», «есть», «есть» и «поэтому» — делают всю работу.

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

• Объект — это то, что он есть (Закон тождества)
• Ни одно утверждение не может быть одновременно истинным и ложным (Закон не- противоречие)
• Каждое утверждение истинно или ложно (Закон исключенного среднего)

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

Аксиоматический метод Аристотеля повлиял на еще более известную книгу Евклида « Элементы », которая, по оценкам, уступает только Библии по количеству напечатанных изданий.

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

Со времени публикации статьи Шеннона на физическом уровне компьютеров был достигнут огромный прогресс, включая изобретение транзистора в 1947 году Уильямом Шокли и его коллегами из Bell Labs. Транзисторы представляют собой значительно улучшенные версии электрических реле Шеннона — наиболее известного способа физического кодирования логических операций.В течение следующих 70 лет полупроводниковая промышленность упаковывала все больше и больше транзисторов в меньшие пространства. В iPhone 2016 года около 3,3 миллиарда транзисторов, каждый из которых представляет собой «релейный переключатель», как те, что изображены на диаграммах Шеннона.

В то время как Шеннон показал, как отображать логику в физическом мире, Тьюринг показал, как проектировать компьютеры на языке математической логики. Когда Тьюринг писал свою статью в 1936 году, он пытался решить «проблему принятия решения», впервые обозначенную математиком Дэвидом Гильбертом, который спросил, существует ли алгоритм, который мог бы определить, истинно или ложно произвольное математическое утверждение.В отличие от статьи Шеннона, статья Тьюринга носит сугубо технический характер. Его основное историческое значение заключается не в ответе на проблему принятия решения, а в шаблоне для компьютерного дизайна, который он предоставил по ходу дела.

Тьюринг работал в традициях, восходящих к Готфриду Лейбницу, философскому гиганту, который разработал исчисление независимо от Ньютона. Среди многочисленных вкладов Лейбница в современную мысль одной из самых интригующих была идея нового языка, который он назвал «универсальной характеристикой», который, как он представлял, может представлять все возможные математические и научные знания.Частично вдохновленный религиозным философом 13-го века Рамоном Лулллом, Лейбниц предположил, что язык будет идеографическим, как египетские иероглифы, за исключением того, что символы будут соответствовать «атомарным» концепциям математики и естествознания. Он утверждал, что этот язык даст человечеству «инструмент», который может усилить человеческий разум «в гораздо большей степени, чем оптические инструменты», такие как микроскоп и телескоп.

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

Если бы возникли разногласия, не было бы необходимости в диспуте между двумя философами больше, чем между двумя бухгалтерами. Ибо достаточно было бы взять их карандаши в руки и сказать друг другу: Calculemus — Давайте посчитаем.

Лейбниц не получил возможности разработать свой универсальный язык или соответствующую машину (хотя он изобрел относительно простую вычислительную машину, ступенчатый счетчик). Первая убедительная попытка осуществить мечту Лейбница была предпринята в 1879 году, когда немецкий философ Готлоб Фреге опубликовал свой исторический трактат по логике Begriffsschrift . Вдохновленный попыткой Буля улучшить логику Аристотеля, Фреге разработал гораздо более совершенную логическую систему. Логика, которую сегодня преподают на курсах философии и информатики — логика первого порядка или логика предикатов — является лишь небольшой модификацией системы Фреге.

Фреге считается одним из самых выдающихся философов XIX века. Среди прочего, ему приписывают катализатор того, что известный философ Ричард Рорти назвал «лингвистическим поворотом» в философии. Поскольку философия Просвещения была одержима вопросами знания, философия после Фреге стала одержима вопросами языка.Среди его учеников были два самых важных философа 20-го века — Бертран Рассел и Людвиг Витгенштейн.

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

Формальный язык Фреге — то, что он назвал своим «концептуальным сценарием» — состоит из бессмысленных символов, которыми манипулируют по четко определенным правилам. Языку придается значение только посредством интерпретации, которая указывается отдельно (это различие позже будет называться синтаксисом по сравнению с семантикой). Это превратило логику в то, что выдающиеся компьютерные ученые Аллан Ньюэлл и Герберт Саймон назвали «символьной игрой», «в которую играют бессмысленными токенами по определенным чисто синтаксическим правилам.

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

Как заметил Бертран Рассел: «Математику можно определить как предмет, в котором мы никогда не узнаем, о чем говорим, и насколько то, что мы говорим, является правдой».

Неожиданным следствием работы Фреге стало обнаружение слабых мест в основах математики.Например, книга Евклида Elements — считалась золотым стандартом логической строгости в течение тысяч лет — оказалась полна логических ошибок. Поскольку Евклид использовал обычные слова, такие как «линия» и «точка», он — и столетия читателей — обманывали себя, делая предположения о предложениях, содержащих эти слова. Приведу один относительно простой пример: в обычном использовании слово «линия» подразумевает, что если вам даны три различные точки на линии, одна точка должна находиться между двумя другими.Но когда вы определяете «линию», используя формальную логику, оказывается, что «промежуточность» также должна быть определена — то, что Евклид упустил из виду. Формальная логика позволяет легко обнаружить подобные пробелы.

Осознание этого привело к кризису в основах математики. Если Elements — библия математики — содержали логические ошибки, то в каких других областях математики тоже? А как насчет таких наук, как физика, которые были построены на основе математики?

Хорошая новость заключается в том, что те же логические методы, которые использовались для обнаружения этих ошибок, также можно использовать для их исправления.Математики начали восстанавливать основы математики снизу вверх. В 1889 году Джузеппе Пеано разработал аксиомы для арифметики, а в 1899 году Давид Гильберт сделал то же самое для геометрии. Гильберт также изложил программу формализации оставшейся части математики с особыми требованиями, которым должна удовлетворять любая такая попытка, в том числе:

• Полнота: Должно быть доказательство того, что все истинные математические утверждения могут быть доказаны в формальной системе.
• Разрешимость: Должен существовать алгоритм для определения истинности или ложности любого математического утверждения.(Это « Entscheidungsproblem » или «проблема решения», о которой упоминается в статье Тьюринга.)

Перестройка математики таким образом, чтобы удовлетворять этим требованиям, стала известна как программа Гильберта. Вплоть до 1930-х годов это было в центре внимания основной группы логиков, включая Гильберта, Рассела, Курта Гёделя, Джона фон Неймана, Алонзо Черча и, конечно же, Алана Тьюринга.

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

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

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

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

Это предложение неверно.

Если это правда, то это ложь, а если ложь, то это правда, что ведет к бесконечной петле внутреннего противоречия.

Рассел впервые применил парадокс лжеца в математической логике. Он показал, что система Фреге позволяла выводить противоречащие друг другу наборы:

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

Это стало известно как парадокс Рассела и рассматривалось как серьезный изъян в достижении Фреге. (Сам Фреге был шокирован этим открытием. Он ответил Расселу: «Ваше открытие противоречия вызвало у меня величайшее удивление и, я бы сказал, испуг, поскольку оно пошатнуло основу, на которой я намеревался строить свою арифметику». )

Рассел и его коллега Альфред Норт Уайтхед предприняли наиболее амбициозную попытку завершить программу Гильберта с помощью Principia Mathematica, , опубликованного в трех томах между 1910 и 1913 годами . Метод компании Principia был настолько подробным, что потребовалось более 300 страниц, чтобы доказать, что 1 + 1 = 2.

Рассел и Уайтхед пытались разрешить парадокс Фреге, введя то, что они назвали теорией типов. Идея заключалась в том, чтобы разделить формальные языки на несколько уровней или типов. Каждый уровень может относиться к уровням ниже, но не к их собственным или более высоким уровням. Это разрешило парадоксы самоотнесения, фактически запретив самореференцию. (Это решение не было популярным среди логиков, но оно повлияло на информатику — большинство современных компьютерных языков имеют функции, вдохновленные теорией типов.)

Парадоксы самореференций в конечном итоге показали, что программа Гильберта никогда не может быть успешной. Первый удар был нанесен в 1931 году, когда Гёдель опубликовал свою теперь знаменитую теорему о неполноте, которая доказала, что любая последовательная логическая система, достаточно мощная, чтобы охватить арифметику, должна также содержать утверждения, которые верны, но не могут быть доказаны. (Теорема Гёделя о неполноте — один из немногих логических результатов, получивших широкую популяризацию благодаря таким книгам, как Gödel, Escher, Bach и The Emperor’s New Mind).

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

Ключевое открытие Тьюринга было сделано в первом разделе его знаменитой статьи 1936 года «О вычислимых числах в приложении к проблеме Entscheidungsproblem .Чтобы строго сформулировать проблему решения (« Entscheidungsproblem »), Тьюринг сначала создал математическую модель того, что значит быть компьютером (сегодня машины, которые соответствуют этой модели, известны как «универсальные машины Тьюринга»). Как описывает это логик Мартин Дэвис:

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

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

В качестве побочного продукта он нашел математическую модель универсальной вычислительной машины.

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

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

Это была первая строгая демонстрация того, что любую вычислительную логику, которую можно закодировать аппаратно, можно также закодировать программно. Архитектура, описанная Тьюрингом, позже была названа «архитектурой фон Неймана» — но современные историки в целом согласны с тем, что она пришла из Тьюринга, как, по-видимому, сам фон Нейман.

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

Во время Второй мировой войны эта теоретическая работа была реализована на практике, когда правительственные лаборатории наняли ряд элитных логиков. Фон Нейман присоединился к проекту атомной бомбы в Лос-Аламосе, где он работал над компьютерным дизайном для поддержки физических исследований. В 1945 году он написал спецификацию EDVAC — первого логического компьютера с хранимой программой, который обычно считается исчерпывающим справочником по источникам для современного компьютерного дизайна.

Тьюринг присоединился к секретному подразделению в Блетчли-парке, к северо-западу от Лондона, где он помогал проектировать компьютеры, которые сыграли важную роль в взломе немецких кодов. Самым большим его вкладом в практический компьютерный дизайн была спецификация ACE, или Automatic Computing Engine.

Будучи первыми компьютерами, основанными на логической логике и архитектурах хранимых программ, ACE и EDVAC во многом были похожи. Но у них также были интересные различия, некоторые из которых предвещали современные дискуссии в области компьютерного дизайна.Излюбленные дизайны фон Неймана были похожи на современные процессоры CISC («сложные»), воплощая богатую функциональность в аппаратное обеспечение. Дизайн Тьюринга больше походил на современные RISC («сокращенные») процессоры, сводя к минимуму сложность оборудования и перенося больше работы на программное обеспечение.

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

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

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

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

Это был бы подходящий второй акт в истории компьютеров. Логика зародилась как способ понять законы мышления. Затем это помогло создать машины, которые могли рассуждать в соответствии с правилами дедуктивной логики. Сегодня дедуктивная и индуктивная логика объединяются для создания машин, которые одновременно рассуждают и обучаются.То, что началось, по словам Буля, с исследования «природы и строения человеческого разума», могло привести к созданию новых умов — искусственных умов, — которые когда-нибудь могут соответствовать нашему собственному или даже превзойти его.

без названия

% PDF-1.4 % 1 0 объект > эндобдж 7 0 объект /Заголовок /Тема / Автор /Режиссер / Ключевые слова / CreationDate (D: 20210820095245-00’00 ‘) / ModDate (D: 20080407102737 + 03’00 ‘) >> эндобдж 2 0 obj > эндобдж 3 0 obj > эндобдж 4 0 obj > эндобдж 5 0 obj > эндобдж 6 0 obj > транслировать Акробат Дистиллятор 7.0.5 (Windows) 2008-04-07T10: 27: 37 + 03: 002008-04-07T10: 27: 37 + 03: 00application / pdf