Site Loader

Содержание

«Основы логики: логические величины и формулы»

Урок№1

Где логика?

Οсновы логики:

логические величины и формулы

Цели урока:

Познакомиться с понятием формальная логика

и алгебра логики;

Познакомиться с основными понятиями

алгебры логики: логическая величина,

логическая операция

Для визуализации этапов правильного решения необходимо нажать на прямоугольник c исходным неравенством. Для визуализации ответа необходимо нажать на прямоугольник «Ответ»

Что это?

1. Какой длины эта лента?

2. Прослушайте сообщение.

3. Париж – столица Англии.

4. Назовите устройство ввода информации.

5. Кто отсутствует?

6. Число 11 является простым.

7. Делайте утреннюю зарядку!

8. Сложите числа 2 и 5.

9. Некоторые медведи живут на севере.

Разделите на группы

Не высказывание

Истинное высказывание

Ложное высказывание

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

Алгебра – это раздел математики, предназначенный для описания действий над переменными величинами, которые принято обозначать строчными латинскими буквами, например a, b, x, y и т.д.

Логика (древнегреч. – слово logos, означает «мысль, понятие, рассуждение, закон») — наука о законах и формах мышления.

Логическая переменная — это простое высказывание, содержащее только одну мысль. Её символическое обозначение – латинская буква (A, B, D, F …). Значениями логической переменной могут быть только константы

ИСТИНА и ЛОЖЬ (1 или 0).

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

ЭТАПЫ РАЗВИТИЯ ЛОГИКИ

Аристотель (384-322 гг. до н.э.) – древнегреческий философ, основоположник логики.

Книги:

  • «Категории» «Первая аналитика» «Вторая аналитика»
  • «Категории» «Первая аналитика» «Вторая аналитика»
  • «Категории»
  • «Первая аналитика»
  • «Вторая аналитика»

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

Силлогизм — рассуждение, в котором из заданных двух суждений выводится третье.

Декарт Рене (1596-1650, французский философ, математик) – рекомендовал в логике использовать математические методы.

ЭТАПЫ РАЗВИТИЯ ЛОГИКИ

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

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

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

Буль изобрел своеобразную алгебру – систему обозначений и правил, применимую к всевозможным объектам, от чисел и букв до предложений. Его именем она теперь и называется: алгебра Буля или булева алгебра .

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

Логические функции ( логические формулы) – сложные логические выражения, образованные из простых и связанные логическими операциями И, ИЛИ, НЕ и др.)

Высказывание «Все мышки и кошки с хвостами» является сложным и состоит из двух простых высказываний.

А=«Все мышки с хвостами» и В=«Все кошки с хвостами»

Его можно записать в виде логической функции, значение которой истинно: F(A,B)=A и B

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

Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть только ложно (0 ) или истинно (1).

Логическое высказывание

  • Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать истинно оно или ложно

Для визуализации этапов правильного решения необходимо нажать на прямоугольник c исходным неравенством. Для визуализации ответа необходимо нажать на прямоугольник «Ответ»

Логическое высказывание

Для визуализации этапов правильного решения необходимо нажать на прямоугольник c исходным неравенством. Для визуализации ответа необходимо нажать на прямоугольник «Ответ»

Логическое высказывание

Для визуализации этапов правильного решения необходимо нажать на прямоугольник c исходным неравенством. Для визуализации ответа необходимо нажать на прямоугольник «Ответ»

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

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

1. Отрицание (инверсия)

2. Логическое умножение (конъюнкция)

3. Логическое сложение (дизъюнкция)

4. Разделительная дизъюнкция

5. Следование (импликация)

6. Эквивалентность

14

Выполните тест

«Основные законы логики»:

Д/з § 13

Вопросы 1,2

Решение заданий ЕГЭ по информатике с использованим элементов алгебры логики

В настоящее время на вступительных экзаменах по информатике есть много заданий по теме “алгебра логики”. Цель данного урока – закрепление навыков решения заданий ЕГЭ по информатике с использованием элементов алгебры логики.

Цели урока:

  • Формирование умения применять полученные знания на практике;
  • Развитие умения построения таблиц истинности по заданным формулам;
  • Развитие умения решать текстовые задачи с использованием законов логики.

Задачи урока:

  • Воспитательная – развитие познавательного интереса, логического мышления.
  • Образовательная – повторение основ математической логики, выполнение практических заданий.
  • Развивающая –  развитие логического мышления, внимательности.

Ход урока

Повторение логических операций и законов.
  • Применение логических операций и законов на практике.
  • Объяснение домашнего задания.
  • Сегодня мы с вами завершаем тему “Основы логики” и применим основные логические операции, законы преобразования для решения заданий ЕГЭ по информатике.

    Урок идет параллельно с презентацией. <Приложение1>

    1. Повторение логических операций и законов.

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

    Вопросы:

    1. Основоположник формальной логики?

    Аристотель.

    2. Основоположник алгебры логики?

    Джордж Буль.

    3. Перечислите логические операции:

    ¬ отрицание (инверсия)
    &, /\ конъюнкция (“И”)
    V дизъюнкция (“ИЛИ”)
    логическое следование (импликация)
    равнозначность (эквивалентность)

    4. В чем смысл закона двойного отрицания?

    Двойное отрицание исключает отрицание.

    5. Законы де Моргана (законы общей инверсии).

    Отрицание дизъюнкции является конъюнкцией отрицаний:

    ¬(A V B) = ¬A /\ ¬B

    Отрицание конъюнкции является дизъюнкцией отрицаний:

    ¬(A /\B) = ¬A V ¬B

    6. Закон идемпотентности (одинаковости).

    A V A = A

    A /\ A = A

    7. В чём смысл закона исключения третьего?

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

    A V ¬А= 1

    8. О чём закон противоречия?

    Не могут быть одновременно истинны утверждение и его отрицание:

    A /\ ¬А= 0

    9. Закон исключения констант.

    Для логического сложения:

    A V 1 = 1 A V 0 = A

    Для логического умножения:

    A /\ 1 = A A /\ 0 = 0

    10. Как выразить импликацию через дизъюнкцию?

    А В = ¬A V В

    2. Примение логических операций и законов на практике.

    Пример 1. (Задание А11 демоверсии 2004 г.)

    Для какого имени истинно высказывание:

    ¬ (Первая буква имени гласная -> Четвертая буква имени согласная)?

    1) ЕЛЕНА

    2) ВАДИМ

    3) АНТОН

    4) ФЕДОР

    Решение. Сложное высказывание состоит из двух простых высказываний:

    А – первая буква имени гласная,

    В – четвертая буква имени согласная.

    ¬ (А В) = ¬ (¬A V В) = (¬ (¬А) /\ ¬B) = A /\ ¬B

    Применяемые формулы:

    1. Импликация через дизъюнкцию А ? В = ¬A V В

    2. Закон де Моргана ¬(A V B) = ¬A /\ ¬B

    3. Закон двойного отрицания.

    (Первая буква имени гласная /\ Четвертая буква имени гласная)

    Ответ: 3

    Пример 2. (Задание А12 демоверсии 2004 г.)

    Какое логическое выражение равносильно выражению ¬ (А \/ ¬B)?

    1) A \/ B

    2) A /\ B

    3) ¬A \/ ¬B

    4) ¬A /\ B

    Решение. ¬ (А \/ ¬B)= ¬ А \/ ¬ (¬B)= ¬ А \/ B

    Ответ: 4

    Пример 3.

    Составить таблицу истинности для формулы

    ¬ (B /\ C) V (A/\C B)

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

    ¬ (B /\ C) V (A/\C B)

    2   1   5   3   4

    Составить таблицу истинности.

    Сколько строк будет в вашей таблице? 3 переменных: А, В, С; 23=8

    Сколько столбцов? 5 операций + 3 переменных = 8

    Решение:

    A B C (B /\ C) ¬ (B /\ C) A/\C (A/\C ? B) ¬ (B /\ C) V (A/\C B)
    0 0 0 0 1 0 1 1
    0 0 1 0 1 0 1 1
    0 1 0 0 1 0 1 1
    0 1 1 1 0 0 1 1
    1 0 0 0 1 0 0 1
    1 0 1 0 1 1 1 1
    1 1 0 0 1 0 0 1
    1 1 1 1 0 1 1 1

    Какие ответы получились в последнем столбце?

    Ответ: 1

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

    Решим этот пример аналитическим методом:

    упрощаем выражение

    ¬ (B /\ C) V (A/\C B)= (применим формулу для импликации)

    ¬ (B /\ C) V ¬ (A /\ C) V B = (применим 1 и 2 законы де Моргана)

    (¬B V ¬C) V (¬A V ¬C) V B = (уберём скобки)

    ¬B V ¬C V ¬A V ¬C V B= (применим переместительный закон)

    ¬B V B V ¬C V ¬C V ¬A = (закон исключения третьего, закон идемпотентности)

    1 V ¬С V ¬A = 1 V ¬A = 1 (закон исключения констант)

    Ответ: 1, означает, что формула является тождественно-истинной или тавтологией.

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

    (задание 3 домашнего задания)

    Пример 4.

    В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдёт поисковый сервер по каждому запросу.

    Для обозначения логической операции “ИЛИ” в запросе используется символ I, а для логической операции “И” – символ &.

    А Законы & Физика
    Б Законы I (Физика & Биология)
    В Законы & Физика & Биология & Химия
    Г Законы I Физика I Биология

    Решение:

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

    Ответ: ВАБГ.

    Второй способ предполагает использование графического представления операций над множествами. (Смотри презентацию)

    Пример 5. (Задание А16 демоверсии 2006 г.)

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

    Фамилия Пол Математика Русский язык Химия Информатика Биология
    Аганян ж 82 56 46 32 70
    Воронин м 43 62 45 74 23
    Григорчук м 54 74 68 75 83
    Роднина ж 71 63 56 82 79
    Сергеенко ж 33 25 74 38 46
    Черепанова ж 18 92 83 28 61

    Сколько записей в данном фрагменте удовлетворяют условию

    “Пол=’м’ ИЛИ Химия>Биология”?

    1) 5

    2) 2

    3) 3

    4) 4

    Решение:

    Выбираем записи: Мальчики (двое) и Химия>Биология (трое, но один мальчик, уже взялся 1 раз). В итоге 4 записи удовлетворяют условию.

    Ответ: 4

    Задание 6. (Задание В4 демоверсии 2007 г)

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

    Один считает, что первой будет Наташа, а Маша будет второй.

    Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место.

    Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй.

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

    Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?

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

    Решение:

    Обозначим высказывания:

    Н1 = “первой будет Наташа”;

    М2 = “второй будет Маша”;

    Л2 = “второй будет Люда”;

    Р4 = “четвертой будет Рита”;

    Р3 = “третьей будет Рита”;

    Н2 = “второй будет Наташа”.

    Согласно условию:

    из высказываний 1 болельщика следует, что Н1VМ2 истинно;

    из высказываний2 болельщика следует, что Л2VР4 истинно;

    из высказываний 3 болельщика следует, что Р3VН2 истинно.

    Следовательно, истинна и конъюнкция

    (Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = 1.

    Раскрыв скобки получим:

    (Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = (Н1/\Л2V Н1/\Р4 V М2/\Л2 V М2/\Р4) /\ (Р3VН2)=

    Н1/\ Л2/\Р3 V Н1/\Р4/\Р3 V М2/\Л2/\Р3 V М2/\Р4/\Р3 V Н1/\Л2/\Н2 V Н1/\Р4/\Н2 V М2/\Л2/\Н2 V М2/\Р4/\Н2 = Н1/\ Л2/\Р3 V 0 V 0 V 0 V 0 V 0 V 0 V= Н1/\ Л2/\Р3

    Наташа-1, Люда-2, Рита-3, а Маша-4.

    Ответ: 1423

    3. Объяснение домашнего задания.

    Задание 1. (Задание В8 демоверсии 2007г)

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

    Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – &.

    А волейбол | баскетбол | подача
    Б волейбол | баскетбол | подача | блок
    В волейбол | баскетбол
    Г волейбол & баскетбол & подача

    Задание 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. Докажем второй закон де Моргана с помощью таблицы истинности. Построим таблицу истинности для левой и правой части закона.

    xyx ∨ y¬ (x ∨ y)¬ x¬ y¬ x ∧ ¬ y
    0001111
    0110100
    1010010
    1110000

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

    Пример 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
    Равенство доказано.

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

    Логическое следование — это отношение, существующее между посылками и выводимыми из них заключениями, которое характеризуется тем, что заключение с необходимостью (обоснованно) следует из посылок. Правила логического следования вырабатываются с таким расчётом, чтобы из истинных посылок получались истинные следствия. Для современной логики характерно то, что класс этих правил устанавливается посредством тех или иных интерпретаций логических исчислений. Хотя логическое следование относится к числу фундаментальных, исходных понятий логики (см. Логика), оно не имеет точного универсального определения; в частности, описание его с помощью слов «выводимо», «вытекает» и тому подобных содержит неявный круг, поскольку последние являются синонимами слова «следует». Понятие «логическое следование» обычно характеризуется через связи с другими логическими понятиями, и прежде всего через понятия логического закона (см. Закон логический) и модели (см. Модель).

    Один из основоположников современной логики А. Тарский в 1936 году в работе с характерным названием «О понятии логического следования» писал: «Предложение X логически следует из предложений класса К, если и только если каждая модель класса К есть также модель предложения X». В связи с этим важный смысл приобретает следующий вопрос: что значит для заключения A следовать из посылок Z? Общепринятым считается следующий принцип: A следует из посылок Z, если и только если любой случай, в котором каждая посылка в Z является истинной, есть случай, в котором A истинна. Основной замысел Тарского состоял в том, чтобы дать определение логического следования, применимого для очень широкого класса рассуждений, причём, как оказалось, настолько широкого, что возникают проблемы уже иного уровня, относящиеся скорее к вопросу о том, что есть логика.

    Логическое следование можно представить как отношение между некоторым множеством высказываний Г (гипотез) и высказыванием B (заключением), отображающее тот факт, что, в силу только логической структуры названных высказываний и, значит, независимо от их содержания нельзя приписать всем высказываниям из Г значение истинно, не будучи при этом быть вынужденным приписать это значение и высказыванию B. В этом случае говорят о логическом следовании B из Г в семантическом смысле и записывают этот факт как утверждение Г ⊧ B, читаемое: из Г семантически следует B.

    В формализованных логических теориях (исчислениях) выражение Г ⊧ B обозначает, что формула B этого исчисления в рамках принятой семантики (см. Семантика) является истинной (обобщённо для многозначных логик: принимает выделенное значение) всегда, когда являются истинными (принимают выделенные значения) все формулы из Г.

    В рамках логики, фиксирующей нормы логических рассуждений с помощью формализованных теорий (логических исчислений), говорят об отношении логического следования в смысле выводимости B из Г в некотором исчислении Т. Символически это записывают как ГB с указанием, если необходимо, о каком исчислении идёт речь. ГB представляет собой метаутверждение о существовании построенной по определённым правилам конечной последовательности формул, называемой выводом из гипотез, в которой последняя формула есть B. При наличии такой последовательности и говорят о логическом следовании B из Г в смысле выводимости. Если при построении последовательности оказывается возможным обойтись без использования посылок, то говорят, что B логически следует из пустого списка гипотез, что принимают как факт его логической доказуемости, в том смысле, что B является теоремой исчисления Т (символически: ⊢ B).

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

    В классической логике множества верных утверждений вида ГB и Г ⊧ B совпадают в том смысле, что каждому ГB соответствует Г ⊧ B и наоборот.

    Выражение ⊧ B трактуется как утверждение о семантической истинности (общезначимости, тавтологичности B). Из понимания логического следования в семантическом смысле вытекает, что в случае семантической истинности B, мы должны признавать верным Г ⊧ B и A ⊧ B для любых Г и A. Иными словами, общезначимая формула следует из любой. Ясно также, что из всякой противоречивой (тождественно ложной) формулы A (a также из противоречивой совокупности формул Г) следует произвольная формула B. При понимании логического следования в смысле выводимости мы должны признавать верным всякое утверждение A ⊢ B, в котором B — теорема исчисления, или A — отрицание теоремы.

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Формула называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией элементарных конъюнкций. ДНФ записываются в виде A1 A2An, где каждое Ai — элементарная конъюнкция. Например, x2x1 & x3, x2 & x2x1 & x2— дизъюнктивные нормальные формы.

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

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

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

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

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

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

    Теорема. Пусть — f (x1, x2, …, xn)булева функция от 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 лет, который не имеет длинной седой бороды”.


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



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

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


    Пример

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

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

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


    Пример

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

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

      A     B    A -> B  A <-> B
    T T T T
    T F F F
    F T T F
    F F T T

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

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


    Пояснительная записка.

    Одна из задач профильной школы — содействовать воспитанию нового поколения, отвечающего по своему уровню развития и образу жизни условиям информационного общества. Данный элективный курс актуален т.к. он выполняет основные задачи профильной школы.
    Эта программа предназначена для проведения элективных курсов по информатике с учащимися 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 веке. Пионерами математической логики стали философы-математики, в первую очередь Джордж Буль и Готлоб Фреге, которые сами были вдохновлены мечтой Лейбница об универсальном «языке понятий» и древней логической системой Аристотеля.

    Слушайте аудиоверсию этой статьи: Особые истории, читайте вслух: загрузите приложение Audm для своего iPhone.

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

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

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

    «Математику можно определить как предмет, в котором мы никогда не знаем, о чем говорим».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Фрагмент Elements (Wikimedia Commons)

    Хотя якобы о геометрии, Elements стал стандартным учебником для обучения строгому дедуктивному мышлению. (Авраам Линкольн однажды сказал, что он научился здравой правовой аргументации, изучая Евклида.) В системе Евклида геометрические идеи были представлены в виде пространственных диаграмм.Так продолжали практиковаться в геометрии, пока Рене Декарт в 1630-х годах не показал, что геометрию вместо этого можно представить в виде формул. Его «Рассуждение о методе » было первым учебником по математике на Западе, который популяризировал то, что сейчас является стандартным алгебраическим обозначением — x, y, z для переменных, a, b, c для известных величин и так далее.

    Алгебра Декарта позволила математикам выйти за рамки пространственной интуиции и манипулировать символами, используя точно определенные формальные правила. Это сместило доминирующий вид математики с диаграмм на формулы, что привело, среди прочего, к развитию исчисления, изобретенного примерно через 30 лет после Декарта, независимо Исааком Ньютоном и Готфридом Лейбницем.

    Целью Буля было сделать для логики Аристотеля то, что Декарт сделал для евклидовой геометрии: освободить ее от ограничений человеческой интуиции, придав ей точную алгебраическую нотацию. Приведу простой пример, когда Аристотель писал:

    Все люди смертны.

    Boole заменил слова «люди» и «смертные» на переменные, а логические слова «все» и «есть» — на арифметические операторы:

    x = x * y

    Что можно интерпретировать как « Все в наборе x также есть в наборе y .

    Законы мысли создали новую научную область — математическую логику, которая в последующие годы стала одной из самых активных областей исследований математиков и философов. Бертран Рассел назвал «Законы мышления » «работой, в которой была открыта чистая математика».

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

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

    Отображение Шеннона электрических цепей в символическую логику (Университет Вирджинии)

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

    Сумматор Шеннона (Университет Вирджинии )

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

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

    Со времени публикации статьи Шеннона на физическом уровне компьютеров был достигнут огромный прогресс, включая изобретение транзистора в 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

  • без названия
  • uuid: ce4cf48b-3f0e-452b-8a9e-da4e77630a15uuid: a2f4d8c0-7164-4244-87dc-494ebdc37baa конечный поток эндобдж 8 0 объект > эндобдж 9 0 объект > эндобдж 10 0 obj > эндобдж 11 0 объект > эндобдж 12 0 объект > эндобдж 13 0 объект > эндобдж 14 0 объект > эндобдж 15 0 объект > эндобдж 16 0 объект > эндобдж 17 0 объект > эндобдж 18 0 объект > эндобдж 19 0 объект > эндобдж 20 0 объект > эндобдж 21 0 объект > эндобдж 22 0 объект > эндобдж 23 0 объект > эндобдж 24 0 объект > / ProcSet [/ PDF / Text / ImageC / ImageB / ImageI] >> эндобдж 25 0 объект > транслировать x ڝ Xn + 7 ++ zEhwͮ «cwӠ ~ IQ4 $ q`DI | J | _b- e9Rǯ |?> -_ ~ q} J $ WCфLzO $ jYZL # km * 4I ܿ z} M71») ց ~ !; u [Xe̓ | 6 , pe bZ 5aaq [\ ~ wdtChFǦr ~ # \ i f [Y $ V4r / ګ̲ vUYE0PTC ‰ / pcKDjC * i * U΃: OB} Pm @ F8]? 0 / Tqb! `@ & IVXjm2C4 * Vu ی Zo | X¤ ُ ^ 6 ۊ hL_ ݂ jzt.GN> JG * jl} k ױ IjTHg ((m * Lw (v ; \ z * Uh PӦ`qDTZÉOS18’K, Vxmygdd * lR4w-q

    Математическая логика для информатики (второе издание) — предисловие и содержание.

    Предисловие

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

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

    Книга предназначена для студентов бакалавриата по информатике. Никаких специальных математических знаний не предполагается, кроме неформальной теории множеств, кратко изложенной в приложении, но используются элементарные знания концепций из информатики (графики, языки, программы). Приведены реализации многих алгоритмов на языке Prolog; для студента, изучающего информатику, изучение конкретной программы может усилить изучение абстрактного алгоритма. Идеальный курс логики мог бы дополнить теорию этой книги практическим изучением логического программирования.

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

    Глава 1 является вводной и рассматривает темы книги. Приложение A суммирует элементарную теорию множеств, которую должен знать читатель, а приложение B содержит справочник по литературе. Остальная часть книги охватывает пять основных тем:

    • Исчисление высказываний (главы 2, 3, 4).
    • Исчисление предикатов (главы 5, 6).
    • Разрешение и логическое программирование (главы 7, 8).
    • Спецификация и проверка программы (главы 9, 10).
    • Временная логика (главы 11, 12).

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

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

    Исчисление высказываний и предикатов — центральные темы в логике, и им следует учить в любом курсе. Остальные три темы не зависят друг от друга, и преподаватель может выбирать или переставлять темы по своему усмотрению. Разделы, отмеченные *, содержат продвинутый материал, который можно пропустить на начальных курсах бакалавриата, а также интересные результаты, представленные без доказательств, выходящие за рамки этой книги.Разделы, помеченные буквой P, содержат программы на Прологе. Печатные программы — это только фрагменты; полный исходный код программ (включая подпрограммы для ввода-вывода и тестирования) доступен в Интернете. Программы были запущены в бесплатной реализации SWI Prolog, но должны работать в любой реализации стандарта Prolog.

    Второе издание полностью переписано. Основные дополнения — это разделы, посвященные диаграммам двоичных решений, программированию логики ограничений и полноте логики Хоара.Одно любопытство: я использовал Великую теорему Ферма как пример формулы, истинность которой неизвестна. С тех пор Эндрю Уайлс доказал теорему! Я решил заменить его гипотезой Гольдбаха.

    Содержание

    1 Введение
    1.1 Истоки математической логики
    1.2 Исчисление высказываний
    1.3 Исчисление предикатов
    1.4 Доказательство теорем и логическое программирование
    1.5 Системы логики
    1.6 Упражнение

    2 Исчисление высказываний: формулы, модели, таблицы
    2.1 Булевы операторы
    2.2 Формулы высказываний
    2.3 Интерпретации
    2.4 Логическая эквивалентность и подстановка
    2.5 Выполнимость, валидность и последствия
    2.6 Семантические таблицы
    2.7 Обоснованность и полнота
    2.8 Реализация
    2.9 Упражнения

    3 Исчисление высказываний: дедуктивные системы
    3.1 Дедуктивные доказательства
    3.2 Система Генцена G
    3.3 Система Гильберта H
    3.4 Обоснованность и полнота H
    3.5 Проверка доказательства
    3.6 Варианты форм дедуктивных систем
    3.7 Упражнения

    4 Исчисление высказываний: разрешение и BDD
    4.1 Разрешение
    4.2 Диаграммы двоичных решений (BDD)
    4.3 Алгоритмы на BDD
    4.4 Сложность
    4.5 Упражнения

    5 Исчисление предикатов: формулы, модели, таблицы
    5.1 Отношения и предикаты
    5.2 Формулы предикатов
    5.3 Интерпретации
    5.4 Логическая эквивалентность и подстановка
    5.5 Семантические таблицы
    5.6 Реализация
    5.7 Конечные и бесконечные модели
    5.8 Разрешимость
    5.9 Упражнения

    6 Исчисление предикатов: дедуктивные системы
    6.1 Система Генцена G
    6.2 Система Гильберта H
    6.3 Реализация
    6.4 Полные и разрешимые теории
    6.5 Упражнения

    7 Исчисление предикатов: разрешение
    7.1 Функции и термины
    7.2 Формы претензий
    7.3 Модели Хербранда
    7.4 Теорема Хербранда
    7.5 Разрешение по основанию
    7.6 Замена
    7.7 Объединение
    7.8 Общее разрешение
    7.9 Упражнения

    8 Логическое программирование
    8.1 Формулы как программы
    8.2 SLD-разрешение
    8.3 Пролог
    8.4 Параллельное логическое программирование
    8.5 Программирование с ограничениями
    8.6 Упражнения

    9 Программы: семантика и проверка
    9.1 Введение
    9.2 Семантика языков программирования
    9.3 Дедуктивная система HL
    9.4 Верификация программы
    9.5 Синтез программы
    9.6 Обоснованность и полнота HL
    9.7 упражнений

    10 Программы: формальная спецификация с Z
    10.1 Пример: сигнал светофора
    10.2 Z-нотация
    10.3 Пример: семантические таблицы
    10.4 Упражнения

    11 Временная логика: формулы, модели, таблицы
    11.1 Введение
    11.2 Синтаксис и семантика
    11.3 Модели времени
    11.4 Семантические таблицы
    11.5 Реализация семантических таблиц
    11.6 Упражнения

    12 Временная логика: дедукция и приложения
    12.1 Дедуктивная система L
    12.2 Обоснованность и полнота L
    12.3 Другая темпоральная логика
    12.4 Спецификация и проверка программ
    12.5 Проверка модели
    12.6 Упражнения

    Математическое образование: корни информатики

    4 причины, почему математика имеет значение для компьютерных наук

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

    1. Математика учит пониманию и общению с помощью абстрактного языка.

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

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

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

    2. Математика учит работать с алгоритмами.

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

    Это слово может чаще использоваться в информатике, но большинство студентов сначала используют алгоритмы в математике. Например, рассмотрим уравнение типа 5 + x = 7.Студенты учатся находить неизвестное слагаемое, вычитая известное слагаемое из суммы. Это алгоритм, который студенты быстро учатся применять к новым задачам и реализовывать разными способами.

    3. Математика учит студентов анализировать свою работу.

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

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

    4. Помимо общих навыков, информатика по-прежнему включает в себя много математики.

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

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

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

    Более эффективный подход к математическому образованию

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

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

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

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

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

    Слишком часто учащимся разрешают отказаться от математики, не понимая, почему математика имеет значение. Мы хотим, чтобы наши ученики подрастали, чтобы стать следующими лидерами в области компьютерных наук и STEM-карьеры в целом. Но мы должны признать, что, пока мы сокращаем математическое образование наших учеников, мы упускаем важную часть уравнения.

    Логика и доказательство

    Обратите внимание, что информация о проведении курса будет обновлена ​​в соответствии с текущими инструкциями ближе к началу Михайловского семестра.

    Обзор

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

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

    Результаты обучения

    Ожидается, что по окончании курса студенты:

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

    Синопсис

    Логика высказываний (7 лекций).

    1. Введение. История математической логики в информатике.
    2. Синтаксис и семантика логики высказываний.Проблема SAT. Перевод проблем с ограничениями в SAT.
    3. Логическая эквивалентность и алгебраические рассуждения. CNF и DNF.
    4. Полиномиальные алгоритмы: формулы Рога, 2-SAT, WalkSAT и XOR-предложения.
    5. Резолюция: обоснованность и полнота опровержения.
    6. DPLL, изучение разделов, улучшения, стохастическое разрешение.
    7. Теорема компактности.

    Логика первого порядка (9 лекций).

    1. Подписи, структуры и оценки.
    2. Примеры: графики, деревья, строки, реляционные базы данных и системы счисления.
    3. Prenex нормальная форма и сколемизация.
    4. Модели Herbrand и разрешение грунта.
    5. Унификация и разрешение для логики предикатов
    6. Неразрешимость выполнимости.
    7. Логические теории, исключение кванторов
    8. Автоматические конструкции.
    9. Игры Эренфойхта-Фрейса.

      Syllabus

      • Синтаксис логики высказываний.Таблицы истинности.
      • Horn-SAT и 2-SAT.
      • Разрешение. DPLL процедура.
      • Теорема компактности.
      • Синтаксис и семантика логики первого порядка.
      • Prenex нормальная форма и сколемизация.
      • Модели Herbrand и разрешение грунта.
      • Унификация и разрешение для логики предикатов.
      • Неразрешимость выполнимости для логики первого порядка.
      • Разрешаемые теории, включая линейную арифметику.
      • Автоматические конструкции.
      • Игры Эренфойхта-Фрейса.

      Список для чтения

      Основной текст:

      • Логика для компьютерных ученых . Уве Шонинг. Современная классика Биркойзера, перепечатка издания 1989 года.

      Дополнительные тексты:

      • Логика в информатике: моделирование и рассуждения о системах , 2-е издание, М. Хут и М. Райан. Cambridge University Press, 2004.
      • .
      • Математическая логика для компьютерных наук , 3-е издание, М.Бен-Ари. Springer, 2012.
      • .
      • Справочник по практической логике и автоматизированному мышлению , Дж. Харрисон. Издательство Кембриджского университета, 2009.

      Дополнительная литература:

      • Гедель, Эшер, Бах: вечная золотая коса , Д. Хофштадтер. Основные книги, 1979.
      • «Логикомикс: эпический поиск истины» , А. Доксиадис и К. Пападимитриу. Bloomsbury Publishing PLC, 2009.
      • .

      Математическая логика.Логика использовалась в тысячах… | Брэндон Скерритт | Заметки по информатике

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

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

      Предложения могут быть только верными или ложными.

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

      Существует около 500 000 способов представления логических символов, поэтому вот наиболее распространенные способы

      Символ в логике

      ¬ или! или ~

      Символ в электронике

      Что он делает

      Инвертирует то, что когда-либо было введено в него.или И или,

      Символ в электронике

      Что он делает

      Принимает> 1 входов, и если оба входа истинны, выдает истину.

      Таблица истинности

      Символ в логике

      В, или «ИЛИ»

      Символ в электронике

      Что он делает

      Принимает> 1 вход, если любой из входов верен чем вывод верен.

      Таблица истинности

      Символ в логике <=> или ≡

      Символ в электронике Нет, это концепция, а не ворота.

      Что он делает A и B должны принимать одно и то же значение истинности

      Таблица истинности

      Символ в логике => или «если a, то b»

      Символ в электронике Нет

      Что Если A истинно, то также и B

      Таблица истинности

      Учитывая интерпретацию, I, мы можем вычислить значение истинности любой формулы P при I. То есть, учитывая версию формулы, которую мы можем вычислить значение истины.

      если I (P) = 1, то мы говорим, что P истинно при интерпретации I. если I (P) = 0, то мы говорим, что P ложно при интерпретации I.

      Этот раздел может помочь читателю в понимании логических головоломок. .

      На острове есть два типа жителей: рыцари, которые всегда говорят правду, и лжецы, которые всегда лгут. Вы идете на остров и встречаете A и B. A говорит, что «B — рыцарь» B говорит, что «Мы двое — противоположные типы»

      Что такое A и B?

      Итак, у нас есть 2 варианта, p: «A — рыцарь»; и q: «B — рыцарь»

      У нас есть 2 варианта, потому что один из них должен быть рыцарем.Либо и A, и B — лжецы, что делает B рыцарем, поскольку он сказал правду, поэтому он солгал, либо A — рыцарь и говорит правду, что B — рыцарь.

      Опции для человека A p верно, то есть утверждение «A — рыцарь» верно. P => Q p ложно, то есть утверждение «A — рыцарь» неверно. ¬P => ¬Q

      Параметры для человека B q истинно, тогда q => ¬pq ложно, тогда ¬q => ¬p

      Теперь нам просто нужно построить таблицу истинности для этих значений

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

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

      Никогда не объединяйте два входных провода

      Если есть 2 отдельных входа, A и B, вы не можете объединить их в один провод.

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

      Если у вас один вход, A, его можно разделить на 2 отдельных провода.

      Выходной провод можно использовать как вход

      Выходной провод можно использовать как вход.

      Ни один из выходных сигналов ворот не может в конечном итоге возвращаться в эти ворота.

      Никакие ворота не могут зацикливаться сами по себе.

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

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

      Две схемы эквивалентны, если они производят один и тот же вывод при одном и том же вводе.

      2 формулы эквивалентны, если они имеют одинаковое значение истинности при каждой возможной интерпретации.

      Символ «≡» используется для обозначения отношения эквивалентности.

      Факты

      рефлексивно ≡ транзитивно симметрично

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

      Коммуникативный закон

      AB = BA, A + B = B + A

      Примеры: 6 * 2 = 12 и 2 * 6 = 12 3 + 4 = 7 и 4 + 3 = 7

      Ассиокативный закон

      a (bc) = ab (c) = abc

      Примеры: (2 + 4) + 5 = 6 + 5 = 11 2 + (4 + 5) = 2 + 9 = 11

      Распределительный закон

      a (b + c) = ab + ac

      Пример: 3 × (2 + 4) = 3 * 6 = 18 3 × 2 + 3 × 4 = 6 + 12 = 18

      Законы Деморгана

      (A ∪ B) ‘= (A)’ ∩ (B) ‘Первый закон гласит, что дополнение к объединению двух множеств является пересечением дополнений.

      (A ∩ B) ’= (A)’ ∪ (B) ’Второй закон гласит, что дополнение пересечения двух множеств является объединением дополнений.

      Чтобы получить хороший пост в блоге о понимании этих законов, нажмите (здесь) [https://brilliant.org/wiki/de-morgans-laws/]

      Разные правила

      Not Not Not A = AA или A и B = AA или нет A и B = A и B (A или B) (A или C) = A или B и C

      Что делать дальше С этого момента превратите схему в логическое выражение и упростите его используя правила выше., v или ¬.

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

      Символ в логике

      Нет

      Символ в электронике

      Что он делает

      Элемент XOR принимает> 1 вход и выполняет исключительную дизъюнкцию. Выход элемента XOR истинен только в том случае, если один из его входов отличается от другого входа.

      Таблица истинности

      Символ в логике

      Нет

      Символ в электронике

      Что он делает

      Логический элемент И-НЕ принимает> 1 входа, а выход является противоположным логическому элементу И.Выходные данные являются истинными, когда один или несколько, но не все его входные данные являются ложными.

      Таблица истинности

      Все логические функции могут быть созданы с использованием вентилей XOR или NAND.

      Двоичная — это система счисления, состоящая из 0 и 1.

      Преобразование десятичного числа в двоичное

      В качестве альтернативы вы можете запомнить степени 2. 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024… А затем преобразовать число в двоичное , скажем, 6, вы строите это из разных сил.Итак, 6 — это 011, а затем обратное, 110

      Двоичное сложение

      Что-то, что вам нужно знать в двоичном формате 0 + 0 = 0 1 + 0 = 1 0 + 1 = 1 1 + 1 = 10

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

      полусумматор

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

      Примечание. Полусумматор Бориса слишком сложен, вы можете добиться того же, заменив 3 его логических элемента одним элементом XOR.

      Таблица истинности

      Полный сумматор

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

      Посмотрите это видео для лучшего понимания

      Обозначение черного ящика

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

      4-битный сумматор

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

      Компьютерное представление отрицательных целых чисел

      Для представления целых чисел используется фиксированное количество бит: 8, 16, 32 или 64 бит .Целое число без знака может занимать все доступное пространство.

      Вы можете «подписать» двоичное число, чтобы указать, отрицательное оно или нет. Например, число 10 может быть представлено в 8-битном формате как 00001010, а -10 может быть представлено в 8-битном формате как 10001010

      Но это иногда вызывает проблемы, например, 10000000 представляет -0. Whaaatt ?? Отрицательный 0? Да! Это верно, и это именно та проблема, которую это вызывает.

      Здесь вступает в игру дополнение 2.

      Дополнение до двоек

      Преобразование десятичного числа в двоичное дополнение

      1) Преобразуйте число в двоичное, пока игнорируйте знак.Итак, 5 — это 0101, а -5 — это 0101.

      2) Если число положительное, то все готово, дальше идти не нужно. В противном случае…

      3) Если число отрицательное, то:

      • Найдите дополнение (например, преобразуйте все нули в единицы и все единицы в нули)
      • Добавьте 1 к дополнению

      Итак, инвертируйте все цифры и добавьте 1 . Простой.

      Если вы хотите узнать, почему это работает, щелкните здесь

      Сложение в двоичном формате, повторное посещение

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

      -1 + -3 1111

      • 1101 1100 с переносом 1, идущим влево, его можно игнорировать.

      Вычитание в двоичном формате

      Считайте это сложением, но отрицайте второй операнд. Таким образом, 4–3 — это всего лишь 4 + (-3)

      , что составляет всего

      0100

      Переполнение

      Примером этого является 4 + 7

      0100

      Правильный результат, 9, слишком велик для вписывается в 4-битное представление.

      Если оба входа в сложении имеют одинаковый знак, а выходной знак разный, произошло переполнение.

      Переполнение не может произойти, если знаки различаются.

      LinkedIn | GitHub | Devpost

      Программа обучения логике в информатике

      Курс-PM

      DAT060 / DIT201 Логика в компьютерных науках

      LP1 HT19 (7,5 л.с.)

      Курс предлагается факультетом компьютерных наук и инженерии.

      Контактная информация
      • Экзаменатор и лектор: Thierry Coquand
      • Лектор: Ана Бове
      • Ассистент учителя:
        • Фабиан Рух
        • Начиаппан Валлиаппан

      Цель курса

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

      График

      TimeEdit

      Обзор тем и материалов для чтения за неделю
      неделя Темы Материалы для чтения / разделы книги
      1 Резюме, логика, множества, отношения, функции, индукция устанавливает отношения функции примечания к индукции Структурная индукция
      1.4,2
      2 Естественная дедукция для логики высказываний 1,1–1,3
      3 Семантика логики высказываний, нормальные формы 1,4–1,5 кроме 1.4.2
      4 Естественный вывод и семантика для логики предикатов 2,1–2,4
      5 Неразрешимость логики предикатов 2,5
      6

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

      Гостевая лекция.

      2,6
      7 LTL, CTL 3,2–3,5
      8

      Алгоритмы, характеристика фиксированных точек

      Повтор, старые экзамены

      3,6–3,7

      Курсовая литература

      Логика в компьютерных науках Майкла Хута и Марка Райана, второе издание.

      См. Http://www.cs.bham.ac.uk/research/lics/

      Упражнения, отмеченные звездочкой («*») в учебнике, имеют решения.

      Электронная версия книги доступна в библиотеке Чалмерса.

      Курс-дизайн

      Курс состоит из серии лекций и упражнений.

      Язык обучения — английский.

      Изменения, внесенные с последнего случая
      • Добавлены две дополнительные лекции с резюме по множествам, отношениям, функциям и индукции.
      • Добавлены и дополнительные упражнения / консультации для обсуждения решения задач и предоставления возможности задать вопросы ассистентам.

      Цели обучения и программа

      Ожидается, что по окончании курса студент сможет:

      Знания и понимание:

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

      Компетентность и навыки:

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

      Суждение и подход:

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

      Ссылка на программу

      Экзаменационная форма

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

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

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

      Чалмерс
      U: 0–29
      3: 30-40
      4: 41-50
      5: 51-60
      GU
      U: 0–29
      G: 30-45
      VG: 46-60

      Примечание:

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

      Другими словами, вам разрешено использовать все правила введения и исключения (включая правила для двойного отрицания) и производные правила MT, PBC и LEM, если не указано иное.

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

      Необязательные уступки:

      Будет 5-6 необязательных индивидуальных заданий. Каждое задание дает до десяти баллов, и 10% этих баллов засчитываются как бонусные баллы на письменном экзамене.Эти бонусные баллы действительны в течение всего 19/20 учебного года.

      Первый крайний срок — в учебе третья неделя , то есть четверг , 19 сентября, 15:00 . Вы можете передать их в ящике для возврата у принтеров и туалетов на 6-м этаже (между компьютерным классом ES61 и групповой комнатой EG-6207) или преподавателю на лекции. Пожалуйста, сделайте , а не , отправьте их по электронной почте.

      Решение заданий будет обсуждаться на пятничной тренировочной сессии после подачи.

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

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

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

      Даты экзаменов на 2019/2020 гг .: 29 октября 2019 г., 7 января 2020 г., 17 августа 202 г.

      Оценка курса
      Студенческие представители

      CTH

      • Ади Хрустич (hrustic @ student.chalmers.se)
      • Джи Сон (песня @ student.chalmers.se)
      • Оскар Вигрен (vioskar @ student.chalmers.se)
      • Карл Викстрём (karlwik @ student.

    alexxlab

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *