Презентация на тему "Основы математической логики"

Презентация: Основы математической логики
1 из 77
Ваша оценка презентации
Оцените презентацию по шкале от 1 до 5 баллов
  • 1
  • 2
  • 3
  • 4
  • 5
0.0
0 оценок

Комментарии

Нет комментариев для данной презентации

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


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

Аннотация к презентации

Скачать презентацию (2.7 Мб). Тема: "Основы математической логики". Содержит 77 слайдов. Посмотреть онлайн. Загружена пользователем в 2017 году. Оценить. Быстрый поиск похожих материалов.

  • Формат
    pptx (powerpoint)
  • Количество слайдов
    77
  • Слова
    другое
  • Конспект
    Отсутствует

Содержание

  • Презентация: Основы математической логики
    Слайд 1

    Основы математической логики

  • Слайд 2

    Булевы функции от одного, двух аргументов и от n аргументов

  • Слайд 3

    Булевы функции. Канонический многочлен Жегалкина

  • Слайд 4

    Булевы функции от одного аргумента

    Булевой функцией от одного аргумента называется функция f, заданная на множестве из двух элементов и принимающая значения в том же двухэлементном множестве. f :{0,1} → {0,1}

  • Слайд 5

    f0 (x) = 0 (функция, тождественно равная 0) f1 (x) = x (тождественная функция) f2 (x) = x’ (функция отрицания) f3 (x) = 1 (функция, тождественно равная 1)

  • Слайд 6

    Булевы функции от двух аргументов

    Булевой функцией от двух аргументов называется функция g, заданная на множестве {0,1} ×{0,1} и принимающая значение в двухэлементном множестве {0,1}

  • Слайд 7

    Сумма по модулю два

    Сумма по модулю два (строгая дизъюнкция) двух переменных x1 иx2 называется булева функция x1x2 которая равна 1 тогда и только тогда, когда равна 1 только одна переменная. x1 x2

  • Слайд 8

    Законы, применимые для суммы по модулю два: Переместительный x1x2=x2x1 Сочетательный (x1x2) x3 = x1(x2 x3) Распределительный конъюнкции x1(x2 x3) = x1x2 x1x3

  • Слайд 9

    Операции с константами: x x = 0 x 0 = х x x = 1 x 1 = х Разложение в СДНФ: x1 x2= x1x2 x1x2 x1 x2= x1 x2= x1 x2

  • Слайд 10

    Связь между дизъюнкцией с суммой по модулю два: x1 x2 = x1 x2 x1x2 Конъюнкция: x1 x2= x1 x2 (x1 x2)

  • Слайд 11

    Логический элемент М2 – сумма по модулю два

    На практике в электронике реализовать сложно. Элемент М2 реализуют из простых устойчивых элементов: И, ИЛИ, НЕ.

  • Слайд 12

    Применение

    Для проверки результатов сложения в двоичном сумматоре для системы контроля и исправления ошибок: 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = (1)0

  • Слайд 13

    Почему «сумма по модулю два»?

    Остаток от деления целых чисел М на N: M mod N Рассмотрим множество Z2 ={0,1} и произведем операцию: (a + b) mod 2 (0 + 0) mod 2 = 0 (0 + 1) mod 2 = 1 (1 + 0) mod 2 = 1 (1 + 1) mod 2 = 0

  • Слайд 14

    Канонический полином Жегалкина

    f(x1x2…xn) = f0 f1x1 f2x2… fnxn f12x1x2…  f12…nx1x2…xn, f1…fn B = {0,1}

  • Слайд 15

    Пример: F(x1x2x3) = =x1x2x3 x1x2x3 x1x2x3 x1x2x3 = =(1x1)x2(1x3)  x1(1  x2)(1  x3) x1(1  x2)x3 x1x2x3 = =(x2x1x2)(1x3)  (x1 x1x2)(1 x3)  (x1  x1x2)x3 x1x2x3 = =x2x1x2x2x3 x1x2x3x1x1x2x1x3x1x2x3x1x3x1x2x3x1x2x3= = x2x2x3  x1 x1x2x3  x1x2x3 Любую логическую функцию можно единственным образом представить в виде полинома Жегалкина

  • Слайд 16

    2-й способ: Многочлен с неопределенным коэффициентом xy= a bx cy dxy При х=0, у=0, то 0 =а При х=0, у=1, то 0=0  с,  с=0 При х=1, у=0, то 1 = b  0,  b=1 При х=1, y=1, то 0 = 1  d,  d=1 хy = x  xy

  • Слайд 17

    Функционально замкнутые классы

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

  • Слайд 18

    Класс функций, сохраняющих 0 (К0)

  • Слайд 19

    Важнейшие замкнутые классы. Теорема Поста

  • Слайд 20
  • Слайд 21

    Приложение функций алгебры логики к анализу и синтезу релейно контактных схем

  • Слайд 22
  • Слайд 23

    Логика предикатов

  • Слайд 24

    Основные понятия, связанные с предикатами

  • Слайд 25

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

  • Слайд 26

    n- местным предикатом называется предложение, содержащее n предметных переменных х1, х2, … ,хn. Переменные выбираются из множества значений М1, М2, … Мn. При этом предикат превращается в высказывание. P(x1, x2, …, xn) – функция высказывания Примеры: Река х впадает в озеро Байкал. – одноместный предикат, определенный на множестве всех рек. Пусть х = Баргузин, тогда: «Река Баргузин впадает в озеро Байкал» - высказывание истинное Пусть х = Днепр, тогда: «Река Днепр впадает в озеро Байкал» - высказывание ложное

  • Слайд 27

    Пример

    x2+y2 ≤9 Сколько переменных? На каком множестве заданы? При какой паре чисел принимает истинное значение? При какой паре чисел принимает ложное значение? 2 R, R 2, 2 2, 3

  • Слайд 28

    Классификация предикатов

    Предикат называется тождественно истинным, если при любой подстановке в предложение из множества значений он становится истинным высказыванием. P(x1, x2, …, xn) = 1 Пример: sin2x + cos2x = 1

  • Слайд 29

    Предикат называется тождественно ложным, если при любой подстановке в предложение из множества значений он становится ложным высказыванием. P(x1, x2, …, xn) = 0 Пример:x2 + y2

  • Слайд 30

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

  • Слайд 31

    Примеры: «Город х расположен на берегу реки Волги» «Рыба х живет в высокогорьях» «Рыба х живет в пресном водоеме» «Современный компьютер х обладает операционной системой» «Компьютерная сеть х соединяет у компьютеров»

  • Слайд 32

    Множество истинности предикатов

    Множество истинности предиката – это множество тех значений, при которых предикат превращается в истинное высказывание. Р+ = {(a1, …, an)} : (P(a1, …, an) = 1} Пример: х2 + у2 = 9 Сколько местный это предикат? На каком множестве он простроен? Множество пар действительных чисел, которые являются координатами точек плоскости, образующими окружность радиусом 9

  • Слайд 33

    Равносильность и следование предикатов

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

  • Слайд 34

    Переход от предиката Р1 к равносильному ему предикату Р2 называется равносильным преобразованием 4х – 2 = -3х – 9 4х + 3х = 2 – 9 Х = -1 Ответ: {-1} – множество истинности для данного уравнения

  • Слайд 35

    Следствия предикатов

    Предикат Q называется следствием предиката P, если он превращается в истинное высказывание на множестве значений, включенных в множество истинных значений предиката Р. P+ Q+

  • Слайд 36

    Пример: Q (х1, …, хn) – предикат «множество компьютеров аудитории 22б » Р (х1, …, хn) – предикат «компьютеры колледжа 50»

  • Слайд 37

    Логические операции над предикатами

  • Слайд 38

    Отрицание предиката

    Отрицанием n-местного предиката Р, определенного на множествах М, называется новый n-местный предикат, определенный на тех же множествах . Обозначение P(x1, … xn) Читается «Неверно, что P(x1, … xn)» Пример: Р(хR) = х  3  Р(хR) =  (х  3) = х> 3

  • Слайд 39

    Конъюнкция двух предикатов

    Конъюнкцией n-местного предиката Р, определенного на множествах М и k-местного предиката Q, определенного на множествах L , называется новый (n+k)-местный предикат, определенный на этих множествах . Обозначение P(x1, … xn) Q(y1, … yn) Чтение:«P(x1, … xn) иQ(y1, … yn)» Пример: Р(хR) = х> -3 Q(хR) = х -3  х

  • Слайд 40

    Дизъюнкция двух предикатов

    Дизъюнкцией n-местного предиката Р, определенного на множествах М и k-местного предиката Q, определенного на множествах L , называется новый (n+k)-местный предикат, определенный на этих множествах . Обозначение P(x1, … xn) Q(y1, … yn) Чтение:«P(x1, … xn) илиQ(y1, … yn)» Пример: Р(хR) = х> -3 Q(хR) = х -3  х

  • Слайд 41

    Примеры

    «Х – четное число» «У – простое число» Определены на N

  • Слайд 42
  • Слайд 43

    Кванторные операции над предикатами

  • Слайд 44

    Кванторы. Отрицание предложений с кванторами

  • Слайд 45

    Квантор общности

    Операция над одноместным предикатом, означающая: x(P(x)) – для всех х имеет место Р(х)

  • Слайд 46

    Квантор существования

    Операция над одноместным предикатом, означающая: x(P(x)) – для всех х имеет место Р(х)

  • Слайд 47

    Квантор можно применять и к n-местному предикату, в результате получится n-1) – местный предикат. Переменную, к которой относится квантор, называют связанной, остальные переменные – свободные.

  • Слайд 48

    Какие переменные связанные и какие свободные?

  • Слайд 49

    1.А(x) = "x – наука"; B(x) = "x гуманитарная". Записать словами:  C =x(A(x) B(x)); D =x((A(x)&B(x))). 2. А(x) = "x – рыба"; B(x) = "x дышит жабрами". Записать словами: C =x(A(x)  B(x)); D = x(A(x)&B(x)).

  • Слайд 50

    Он ничего не знает. Некоторые абитуриенты поступили в институт. Студент ответил на некоторые вопросы. Автобус останавливается на всех остановках.

  • Слайд 51

    1. определить, какие переменные свободные, а какие связанные. 2. Даны предикаты: А(x) и B(x). Записать словами предложенные формулы С и D.

  • Слайд 52

    Численные кванторы

  • Слайд 53
  • Слайд 54

    Применение логики предикатов к логико-математической практике

  • Слайд 55

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

  • Слайд 56

    Тождественные преобразования предикатов

  • Слайд 57

    Х - люди F(x) = «блондины»; G(x) = «ездят на машинах» x(F(x)&G(x)) =  x(F(x)& x(G(x) «Для всех людей верно, что они блондины и ездят на машинах» «Все люди блондины и все люди ездят на машинах»  x(F(x)G(x) =  x(F(x)  x (G(x) «Для всех людей верно, что они блондины или ездят на машинах» «Все люди блондины или все люди ездят на машинах» x(F(x)&G(x)) «Неверно для всех людей, что они блондины и ездят на машинах» ( x(F(x)& xG(x)) =  x(F(x)  xG(x) «Неверно, что все люди блондины и все люди ездят на машинах» «Неверно, что все люди блондины или неверно, что все люди ездят на машинах»

  • Слайд 58

    x(F(x)G(x)) =  x(F(x))  x (G(x)) «Есть люди, которые являются блондинами или ездят на машинах» «Есть люди – блондины или есть люди, ездящие на машинах»  x(F(x)&G(x) =  x(F(x)&  x (G(x)) «Есть люди, которые являются блондинами и ездят на машинах» «Есть люди – блондины и есть люди, ездящие на машинах» x(F(x)G(x)) = ( x(F(x))  x (G(x)) = =  x(F(x)) & x(G(x)) «Неверно, что есть люди, которые являются блондинами или ездят на машинах» «Неверно, что есть люди – блондины или есть люди, ездящие на машинах» «Неверно, что есть люди – блондины и есть люди, ездящие на машинах»

  • Слайд 59

    Перенос квантора через отрицание

     x(F(x)) =  x  (F(x)) «Неверно, что все люди – блондины» «Есть люди –не блондины» ( x(F(x)) = x (F(x)) «Неверно, что некоторые люди – блондины» «Для всех людей неверно, что они – блондины»

  • Слайд 60

    Вынос квантора за скобки

     x(F(x)&G) =  x(F(x)) & G «Для некоторых людей верно, что они блондины и машины красного цвета» «Некоторые люди – блондины и машины красного цвета»  x(F(x)  G) =  x(F(x)) G «Для некоторых людей верно, что они блондины или машины красного цвета» «Некоторые люди – блондины или машины красного цвета»  x(F(x)&G) =  x(F(x)) & G «Для всех людей верно, что они блондины и машины красного цвета» «Все люди – блондины и машины красного цвета»  x(F(x) G) =  x(F(x)) G «Для всехлюдей верно, что они блондины или машины красного цвета» «Все люди – блондины или машины красного цвета»

  • Слайд 61

    Принцип математической индукции в предикатной форме

  • Слайд 62

    Элементы теории алгоритмов

  • Слайд 63

    Вычислимые функции и алгоритмы

  • Слайд 64

    Теории алгоритмов

  • Слайд 65
  • Слайд 66

    Свойства алгоритмов

  • Слайд 67
  • Слайд 68

    Простейшие функции

  • Слайд 69
  • Слайд 70

    Рекурсивные функции

  • Слайд 71
  • Слайд 72

    Нормальный алгоритм Маркова. Машина Тьюринга

  • Слайд 73

    Основные определения. Алгоритм Маркова

  • Слайд 74
  • Слайд 75

    Алгоритм Тьюринга

  • Слайд 76
  • Слайд 77
Посмотреть все слайды

Сообщить об ошибке