|
|
|||||||
| |||||||
|
Построение таблиц истинности логических выражений
Похожие презентации:
Пиксельная картинка
Информационная безопасность.
Методы защиты информации
Электронная цифровая подпись (ЭЦП)
Этапы доказательной медицины в работе с Pico. Первый этап
История развития компьютерной техники
От печатной книги до интернет-книги
Краткая инструкция по CIS – 10 шагов
Информационные технологии в медицине
Информационные войны
Моя будущая профессия. Программист
Практическая работа №3
«Построение таблиц истинности
логических выражений»
Основные логические операции
Название логической
операции
Обозначение
Инверсия
«¯»
Конъюнкция
«&»
Дизъюнкция
«V»
Логические операции
Инверсия − это логическая операция, которая преобразует исходное высказывание
в новое, значение которого противоположно исходному.
А=0
инверсия
Ā=1
А=1
инверсия
Ā=0
A
Ā
0
1
1
0
Логические операции
Конъюнкция − это логическая операция, которая объединяет два высказывания в
одно новое, которое будет являться истинным тогда и только тогда, когда оба
А−
А=1
А−
А=0
A
B
A&B
0
0
0
0
1
0
1
0
0
1
1
1
Логические операции
Дизъюнкция − это логическая операция, которая объединяет два высказывания в
одно новое, которое будет являться ложным тогда и только тогда, когда ложны оба
исходных высказывания.
А−
А=1
А−
А=0
A
B
AVB
0
0
0
0
1
1
1
0
1
1
1
1
План построения таблицы истинности
1.
Посчитать n – число переменных в выражении.
2.
Подсчитать общее число логических операций в
выражении.
3.
Установить последовательность логических
операций с учётом скобок и приоритетов.
4.
Определить число столбцов в таблице: число
переменных + число операций.
Заполнить шапку таблицы, включив в неё
переменные и операции в соответствии с
последовательностью.
6.
Определить число строк в таблице (не считая
шапку таблицы): m = 2n.
7.
Выписать наборы входных переменных с учётом
того, что они представляют собой ряд целых nразрядных двоичных чисел от 0 до 2n — 1.
А B C
AVB
(A V B) & C
План построения таблицы истинности
1.
Посчитать n – число переменных в выражении.
(А V B) & C
n=3
План построения таблицы истинности
1.
Посчитать n – число переменных в выражении.
(А V B) & C
2.
Подсчитать общее число логических операций в
выражении.
Количество логических
операций: 2
План построения таблицы истинности
1.
Посчитать n – число переменных в выражении.
(А V B) & C
2.
Подсчитать общее число логических операций в
выражении.
1.
Операции в скобках.
Установить последовательность логических
операций с учётом скобок и приоритетов.
2.
Инверсия.
3.
Конъюнкция.
4.
Дизъюнкция.
3.
План построения таблицы истинности
1.
Посчитать n – число переменных в выражении.
(А V B) & C
2.
Подсчитать общее число логических операций в
выражении.
Количество столбцов: 5.
3.
Установить последовательность логических
операций с учётом скобок и приоритетов.
4.
Определить число столбцов в таблице: число
переменных + число операций.
План построения таблицы истинности
1.
Посчитать n – число переменных в выражении.
2.
Подсчитать общее число логических операций в
выражении.
3.
Установить последовательность логических
операций с учётом скобок и приоритетов.
4.
Определить число столбцов в таблице: число
5.
Заполнить шапку таблицы, включив в неё
переменные и операции в соответствии с
последовательностью.
А B C
AVB
(A V B) & C
План построения таблицы истинности
1.
Посчитать n – число переменных в выражении.
2.
Подсчитать общее число логических операций в
выражении.
3.
Установить последовательность логических
операций с учётом скобок и приоритетов.
4.
Определить число столбцов в таблице: число
переменных + число операций.
5.
Заполнить шапку таблицы, включив в неё
переменные и операции в соответствии с
последовательностью.
6.
Определить число строк в таблице (не считая
шапку таблицы): m = 2n.
А B C
n=3
m = 23 = 8
AVB
(A V B) & C
План построения таблицы истинности
1.
Посчитать n – число переменных в выражении.
2.
Подсчитать общее число логических операций в
выражении.
3.
Установить последовательность логических
операций с учётом скобок и приоритетов.
4.
Определить число столбцов в таблице: число
переменных + число операций.
5.
Заполнить шапку таблицы, включив в неё
переменные и операции в соответствии с
последовательностью.
6.
Определить число строк в таблице (не считая
шапку таблицы): m = 2n.
А B C
AVB
(A V B) & C
План построения таблицы истинности
1.
Посчитать n – число переменных в выражении.
2.
Подсчитать общее число логических операций в
выражении.
3.
Установить последовательность логических
операций с учётом скобок и приоритетов.
4.
Определить число столбцов в таблице: число
переменных + число операций.
Заполнить шапку таблицы, включив в неё
переменные и операции в соответствии с
последовательностью.
6.
Определить число строк в таблице (не считая
шапку таблицы): m = 2n.
7.
Выписать наборы входных переменных с учётом
того, что они представляют собой ряд целых nразрядных двоичных чисел от 0 до 2n — 1.
А B C
AVB
(A V B) & C
План построения таблицы истинности
1.
Посчитать n – число переменных в выражении.
А B C
2.
Подсчитать общее число логических операций в
выражении.
0
0
0
3.
Установить последовательность логических
операций с учётом скобок и приоритетов.
0
0
1
0
1
0
Определить число столбцов в таблице: число
переменных + число операций.
0
1
1
1
0
0
Заполнить шапку таблицы, включив в неё
переменные и операции в соответствии с
последовательностью.
1
0
1
1
1
0
6.
Определить число строк в таблице (не считая
шапку таблицы): m = 2n.
1
1
1
7.
Выписать наборы входных переменных с учётом
того, что они представляют собой ряд целых nразрядных двоичных чисел от 0 до 2n — 1.
4.
5.
AVB
(A V B) & C
План построения таблицы истинности
1.
Посчитать n – число переменных в выражении.
А B C
2.
Подсчитать общее число логических операций в
выражении.
0
0
0
3.
Установить последовательность логических
операций с учётом скобок и приоритетов.
0
0
1
0
1
0
Определить число столбцов в таблице: число
переменных + число операций.
0
1
1
1
0
0
Заполнить шапку таблицы, включив в неё
переменные и операции в соответствии с
последовательностью.
1
0
1
1
1
0
6.
Определить число строк в таблице (не считая
шапку таблицы): m = 2n.
1
1
1
7.
Выписать наборы входных переменных с учётом
того, что они представляют собой ряд целых nразрядных двоичных чисел от 0 до 2n — 1.
4.
5.
8.
AVB
(A V B) & C
Провести заполнение
таблицы по столбцам.
План построения таблицы истинности
1.
Посчитать n – число переменных в выражении.
А B C
2.
Подсчитать общее число логических операций в
выражении.
0
0
3.
Установить последовательность логических
операций с учётом скобок и приоритетов.
0
AVB
(A V B) & C
0
0
0
0
1
0
0
0
1
0
1
0
Определить число столбцов в таблице: число
переменных + число операций.
0
1
1
1
1
1
0
0
1
0
Заполнить шапку таблицы, включив в неё
переменные и операции в соответствии с
последовательностью.
1
0
1
1
1
1
1
0
1
0
6.
Определить число строк в таблице (не считая
шапку таблицы): m = 2n.
1
1
1
1
1
7.
Выписать наборы входных переменных с учётом
того, что они представляют собой ряд целых nразрядных двоичных чисел от 0 до 2n — 1.
4.
5.
8.
Провести заполнение
таблицы по столбцам.
Задание. Составить таблицу истинности следующих выражений:
1.
2.
3.
4.
5.
(неA)&B
A v B&C
(неА) v B&(неC)
(неА) & B&C
Не(неА V не(В&С))
на оценку «3»
на оценку «4»
на оценку «5»
English Русский Правила
1.3: Таблицы истинности и значение «~», «&» и «v»
-
- Последнее обновление
- Сохранить как PDF
- Идентификатор страницы
- 1657
Мы сказали, что «~А» означает не А, «А&В» означает А и В, а «АвВ» означает А или В во всеобъемлющем смысле.
Это должно дать вам довольно хорошее представление о том, что означают связки «~», «&» и «v». Но логики должны быть максимально точными. Поэтому нам нужно уточнить, как мы должны понимать связки еще точнее. Более того, метод, который мы будем использовать для этого, окажется очень полезным для многих других вещей.
Чтобы получить представление, начнем с очень простого случая знака отрицания, ‘~’. Предложение «А» либо истинно, либо ложно. Если «А» истинно, то «~А» ложно. Если «А» ложно, то «~А» истинно. И это все, что вам нужно знать о значении «~». Мы можем выразить это более кратко с помощью таблицы, называемой таблицей истинности :
.Определение таблицы истинности ‘~’
| Чемодан | А | ~А |
| 1 | т | ф |
| 2 | ф | т |
В столбце под «А» перечислены все возможные случаи истинности и ложности «А».
Мы делаем это, описывая случаи в терминах того, что мы называем истинными ценностями . Случай, в котором A истинно, описывается утверждением, что A имеет истинностное значение t. Случай, в котором A ложно, описывается утверждением, что A имеет истинностное значение f. Поскольку А может быть только истинным или ложным, у нас есть только эти два случая. Мы объясняем, как понимать «~», говоря, каково истинное значение «~ A» в каждом случае. В случае 1 ‘~A’ имеет истинностное значение f; то есть ложно. В случае 2 ‘~A’ имеет истинностное значение t; то есть это правда. Хотя то, что мы сделали, кажется тривиальным в этом простом случае, очень скоро вы увидите, что таблицы истинности чрезвычайно полезны.
Давайте посмотрим, как использовать таблицы истинности для объяснения ‘&’. Союз состоит из двух атомарных предложений, поэтому нам нужно рассмотреть четыре случая:
| Чемодан | А | Б | АиБ |
| 1 | т | т | |
| 2 | т | ф | |
| 3 | ф | т | |
| 4 | ф | ф |
Когда «А» истинно, «В» может быть истинным или ложным.
Когда «А» ложно, снова «В» может быть истинным или ложным. Приведенная выше таблица истинности дает все возможные комбинации значений истинности, которые могут иметь вместе «А» и «В».
Теперь мы уточняем, как следует понимать ‘&’, указав значение истинности для каждого случая для составного ‘A&B’:
Определение таблицы истинности ‘&’
| Чемодан | А | Б | АиБ |
| 1 | т | т | т |
| 2 | т | ф | ф |
| 3 | ф | т | ф |
| 4 | ф | ф | ф |
Другими словами, «А и В» истинны, когда истинны конъюнкты «А» и «В».
«А и В» ложны во всех остальных случаях, то есть когда один или оба конъюнкта ложны.
Несколько слов о порядке, в котором я перечислил дела. Если вам интересно, вы можете попробовать угадать рецепт, по которому я заказывала ящики. (Если вы попытаетесь, взгляните также на более сложный пример в разделе 1.5.) Но я не буду останавливаться на объяснениях, потому что все, что важно в порядке, это то, что мы не пропускаем ни одного случая, и все мы перечисляем их. в том же порядке, чтобы мы могли легко сравнить ответы. Так что просто перечислите случаи, как я.
Мы следуем тому же методу, определяя, как понимать «V». Дизъюнкция «AvB» истинна, когда истинны одна или обе дизъюнкции «А» и «В». «AvB» ложно только тогда, когда «A» и «B» оба ложны:
определение таблицы истинности ‘v’
| Чемодан | А | Б | АвБ |
| 1 | т | т | т |
| 2 | т | ф | т |
| 3 | ф | т | т |
| 4 | ф | ф | ф |
Мы определили связки ‘~’, ‘&’ и t’, используя таблицы истинности для специального случая букв предложения ‘A’ и ‘B’.
Но, очевидно, ничего не изменится, если мы будем использовать какую-то другую пару предложений, например «H» и «D».
В этом разделе основное внимание уделяется определениям таблицы истинности ‘~’, ‘&’ и ‘v’. Но попутно я ввел два вспомогательных понятия, с которыми вам нужно быть очень ясными. Во-первых, на Значение истинности Назначение значений истинности с по Буквы предложения , я имею в виду, грубо говоря, строку таблицы истинности, а Таблица истинности представляет собой список всех возможных назначений значений истинности для букв предложения в предложении:
Присвоение значений истинности набору атомарных букв предложений является спецификацией для каждой из букв предложения, следует ли считать букву (для этого присвоения) истинной или ложной. Слово Случай также будет использоваться для «присвоения значений истинности».
Таблица истинности для предложения — это спецификация всех возможных присвоений значений истинности буквам предложения, которые встречаются в предложении, и описание значения истинности предложения для каждого из этих присвоений.
-
Пол Теллер (Калифорнийский университет в Дэвисе). Букварь был опубликован в 1989 году издательством Prentice Hall, после чего его приобрела компания Pearson Education. Компания Pearson Education разрешила прекратить выпуск учебника для начинающих и вернула авторские права профессору Теллеру, который рад сделать его бесплатным для использования в учебных и образовательных целях.
- Наверх
-
- Была ли эта статья полезной?
-
- Тип изделия
- Раздел или Страница
-
- Теги
-
Логика
Логика Представление знанийСначала у нас есть Данные
Затем у нас есть информация — уточненная и инкапсулированная форма данных
Теперь у нас есть Знание — очищенная и инкапсулированная форма информации
Методы представления знаний
Правила производстваСемантические сети
Иерархии включения
Математическая логика
Фреймы
Скрипты
Семантические сети
Ограничения
Реляционные Базы данных
и т.д.
Рассмотрим задачу фермера, который хочет переплыть реку на лодке. у фермера есть коза, немного капусты и лиса. Лодка может одновременно перевозить любое два из вышеперечисленных трех. Как перейти реку?
Обычно правильное представление проблемы — это больше половины пути к решение.
Исходное состояние
| фермер коза капуста лиса |
| пустой |
конечное состояние
| Пустой |
| фермер коза капуста лиса |
различные состояния, в которых мы находимся и соединяем их стрелками
индикация переходов состояний. Полученное изображение можно рассматривать как
семантическая сеть.
Математическая логика (ML)
Преимущества ML:
Идеи, вызревшие веками
Краткость, точность и универсальность
Существует множество доказательств.
Итак, мы знаем, что можно делать, а что нельзя.
Недостатки
Работа с предметом может заставить вас сосредоточиться на логической части, таким образом
отвлечение внимания от проблемы. Методы на основе
ML можно использовать
«низкоуровневого» представления, но часто неадекватны для решения реальных «высокоуровневых» задач.
проблемы уровня».
Что мы здесь узнаем?
1. Более одного типа логики
— Пропозициональная
логика
— логика предикатов
2. Обозначения, используемые в логике
3. Правило вывода
— Modus ponens
— Modus tolens
— Разрешение
4. Методы доказательства
— Доказательство репутацией
— Доказательство резольвентной теоремы
5. Невероятная терминология
Факт — это то, что известно как истина. Факт всегда верен.
Утверждение — это утверждение о том, что нечто является фактом.
Утверждение
может быть ложным.
Правило: «, если за шаблоном(ами) следует» «, затем шаблон(ами) »
Каждый шаблон if является предшествующим шаблоном . Шаблон , затем является последовательным
В вычете , шаблон , если шаблон , и шаблон , затем шаблон .
являются утверждениями.
В системе реакции шаблон , затем
обычно действие (я)
Когда все антецеденты удовлетворены, правило срабатывает.
Логика высказываний
Предложение есть состояние мира, о котором мы хотим сказать что-нибудь. Для удобства каждому предложению дается атомарное имя.
Простые предложения
«Идет дождь» становится ДОЖДЬ. Здесь ДОЖДЬ — простое предложение.
Сложные предложения
~RAINING означает «дождь не идет»
RAINING|SNOWING означает «дождь идет либо
или идет снег»
ДОЖДЬ => ~СОЛНЕЧНОЕ МЕНАС «Если идет дождь, то это не
солнечно»
Логические связки и их приоритет
НЕ ~
СОЕДИНЕНИЕ И
РАЗЪЕДИНЕНИЕ |, V
ПОСЛЕДСТВИЕ =>,
ОБРАТНОЕ <=, ЭКВИВАЛЕНТНОСТЬ <=>
Грамматика:
Вы должны
будьте осторожны здесь.
Каждая книга может определять и использовать свои собственные правила грамматики. Когда ты
делаете домашнее задание и убедитесь, что правила грамматики вы
используются те же правила, что и инструктор. Например,
перечисленные здесь правила могут не совпадать с правилами, перечисленными в вашем тексте
книга.
<верхний> :: = A|…|Z
<нижний> :: = a|…|z
<цифра>
:: = 0|1|2|…|9
<знак пунктуации> : : = ( | )
<логарифмическая связь> : : = & | |
<алфавит> : : = <нижний> | <верхний> | <цифра>
<отрицание> : : = ~<предложение>
<союз> : : =
(<предложение> & … & <предложение>)
и т. д.
Интерпретация
Логическая константа может принимать два возможных значения, а именно T и F
A
пропозициональный язык с n логическими константами имеет 2**н
интерпретации.
Таблицы истинности
Таблицы истинности для отрицания, конъюнкции и дизъюнкции просты, и здесь не обсуждаются.
Таблица истинности для импликации очень важна, и вы должны тщательно понимаю это. Мы будем использовать это соотношение очень часто.
А = > В
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
То есть А => В = ~AVB.
Это очень полезно в доказательствах.
Удовлетворение.
Интерпретация i удовлетворяет предложению s (написано |= i s ) тогда и только тогда, когда i(s) = True.
Пример: Рассмотрим интерпретацию i, определенную следующим образом.
я(р) = Т
i(q) = F
i (r) = T
Эта интерпретация удовлетворяет предложению
(p | q) & (~q | r)
потому что
(Т | Ф) и (~ Ф | Т) = Т
Срок действия
Двойное отрицание:
p < = > ~~p
Законы де Моргана:
~(p & q) < = > (~p | ~q)
~(p | q) < = > (~p & ~q)
Определение следствия:
(p = > q) < = > (~p | q)
Следствие
Распределение:
(p = > (q = >r) ) = > ( (p =
>q) = > (q = > r) )
Тавтологическое Запутывание
Логика предикатов
Учитывать
Если у животного есть перья
тогда это птица
Но как понять, что у чего-то есть перья или что-то птица?
Мы используем предикатов .
Предикаты — это функции, которые отображают аргументы объекта в ИСТИНА или ЛОЖЬ
Чтобы сказать «У альбатроса есть перья», мы можем использовать предикат «Перья» и записывать
Перья (Альбатрос)
Чтобы сказать, что альбатрос — это птица, мы говорим
Птица (Альбатрос)
То есть,
Перья (Альбатрос) и Птица (Альбатрос) являются ИСТИННЫМИ выражениями .
То есть Альбатрос — это то, для чего предикат Перья доволен.
Рассмотрим
~ Перья (Сьюзи).
Сьюзи — это то, для чего НЕ выполняется предикат Feathers.
Аналогично
Мухи (сквигги) и Layseggs (сквигги)
Мухи (сквигги) V Layseggs (сквигги)
Давайте посмотрим на последствия.
Перья(сьюзи) => Птица (сьюзи)
Предположим, мы говорим, что приведенное выше выражение ИСТИННО. Делая это, мы ограничение того, что Сьюзи может обозначать.
возможность 1. И Перья(сьюзи) , и Птица (сьюзи) ИСТИННЫ
вариант 2.
Перья (Сьюзи) и Птица (Сьюзи)
ЛОЖНЫЙ
возможность 3. Feathers(suzie) является ЛОЖНЫМ, но Bird (suzie) является ПРАВДА. В этом случае импликация ИСТИНА
Если Feathers(suzie) равно TRUE, а Bird (suzie) – FALSE, то выражение Feathers(suzie) => Bird (suzie) является ЛОЖНЫМ
Это отражено в приведенной ниже таблице истинности.
Таблицы ПРАВДЫ
Импликация A = > равна ….
| Б Правда | B Ложь | |
| Правда | Истинно | Ложно |
| A Ложно | Истинно | True |
Другой способ взглянуть на это — записать это как
A = > B совпадает с ~A V B
Таблицы истинности для конъюнкции, дизъюнкции и отрицания простой.
Логические связки подчиняются коммутативным, дистрибутивным и ассоциативным
законы.
Они также подчиняются законам ДеМограна
~(A&B) <=> (~A) V (~B)
~(AVB) <=> (~A) & (~B)
Два отрицания уничтожают друг друга.
~(~А) <=> А
Квантификаторы
Перевернутое значение A = универсальный квантификатор
Обратное значение E =
квантор существования
Ax = для всех x
Ex = существует x, то есть существует хотя бы один x
Прочитать выражение
Топор[Перья(x) => Птица(x)]
Любой объект с перьями — это птица.
Для всех x, если у x есть перья,
подразумевает, что x — это птица.
[ ] определяет область квантификатора.
Логическое выражение может быть истинным или ложным. Например, мы можем утверждать, что
Топор[Перья(x) => Птица(x)]
ИСТИНА. Тогда,
Feathers(squigs) => Bird (squigs) тоже ИСТИНА
Некоторые определения
объектов: Из чего состоит мир.
Термы:
Эти объекты термины
Переменные, расположенные над объектами, также являются терминами
Функции также являются терминами.
Аргументами функций являются терма.
Возвращаемые значения представляют собой терма.
Термины — единственное, что может выступать в качестве аргументов предикаты.
Атомные формулы являются индивидуальными предикатами вместе со своими аргументами.
Литералы являются атомарными формулами и инвертированными атомарными формулами
Хорошо сформированные формулы:
Литералы — это wffs
wffsconnectby
~, V, & и => являются wffs.
wffs в окружении
квантификаторы — это wffs.
Предложение: WFF, в котором все переменные, если они есть, находятся внутри области видимости объема соответствующих кванторов является предложением.
Связанный : Переменные, попадающие в область действия квантификатора, сказал быть связанным. В противном случае они свободны.
Следующие
Топор [Перья (x) V ~ Перья (y)]
не является предложением, потому что переменная y не связана.
Слова выражение и wff часто используются взаимозаменяемо.
Переменные могут представлять только объекты; они не могут представлять предикаты в
исчисление предикатов первого порядка.
Правила вывода:
1. Modus ponens
A => B
A
—————
Затем B
логически следует
Предположим, что есть аксиома A => B и другая аксиома A, тогда B логически следует.
Пример: Предположим, нам сказали, что оба следующих выражения истинный.
Перья (Сквиги)
Топор [Перья (x) => Птица (x)]
верны. Нас просят показать, что все интерпретации, которые делают истинные аксиомы также делают истинным следующее выражение.
Птица (сквиг)
Решение: Постановка задачи не в форме, подходящей для Modus
Поненс. Сначала преобразуйте это в ту форму.
Потому что мы имеем дело
с интерпретациями, для которых Feathers(x) => Bird (x) верно для всех x,
должно быть истинным для x=squigs.
Следовательно,
Перья (сквиги)
=> Птица (сквигов)
Перья (сквигов), дано
_____________________________
Птица (сквиг)
QED
2. Разрешение.
Аксиома 1. A V B
Аксиома 2. ~B V C
Тогда A V C
логически следует. Выражение A V C называется резольвентой.
Как это возможно? Предположим, что B истинно. Тогда ~B ложно. Затем, из второе выражение, C должно быть истинным. Тогда верно AVC.
Чтобы это работало, у вас может быть любое количество дизъюнктов. Единственным требованием является что одно разрешающее выражение должно содержать дизъюнктив, являющийся отрицанием дизъюнктны в другом выражении.
Применим решение к задаче о сквигах. Давайте перепишем
Feathers(squigs) => Bird (squigs) as ~ Feathers(squigs) V Bird (squigs)
Мы также знаем
Перья(сквиги)
Сложите эти две вещи вместе;
Перья (сквиги)
~ Перья (сквиг) V Птица (сквиг)
Отбросив два противоречащих друг другу предмета, мы получим Птиц (сквигов).