Математическая логика
Логика использовалась тысячи лет, от философии до математики, а теперь и до искусственного интеллекта. Логика связана с истинностью и ложностью утверждений. Логика, которую мы будем изучать, будет отвечать на вопрос: «когда утверждение следует из набора утверждений?»
Примечание для читателя
Я ранее писал о логике здесь, и поэтому эта статья будет относительно короткой, когда дело доходит до объяснения всего о логике. Если вы хотите понять логику, прочтите, пожалуйста, статью о логике, которую я написал. Это просто расширение того, что мы узнали.
Логика высказываний
Предложения могут быть только верными или ложными.
Интровершения
Интерпретация придает пропозициональному утверждению значение истинности Истина или Ложь. Истина или Ложь могут быть представлены как 0 и 1 соответственно.
Пропозициональные символы
Существует около 500 000 способов представления логических символов, поэтому вот самые распространенные способы.
Нет
Символ в логике
¬ or ! or ~
Символ в электронике
Что он делает
Инвертирует то, что когда-либо было введено в него.
Таблица истинности
Соединение или и
Символ в логике
^ или И или,
Символ в электронике
Что он делает
Принимает ›1 входов, и если оба входа истинны, выдает истину.
Таблица истинности
Дизъюнкция, "или"
Символ в логике
V, or, “OR”
Символ в электронике
Что он делает
Принимает ›1 входов, если любой из входов верен, чем выход истинен.
Таблица истинности
Равенство
Символ в логике ‹=› или ≡
Символ в электронике Нет, это концепция, а не ворота.
Что он делает. А и Б должны иметь одинаковое значение истинности.
Таблица истинности
A B A <=> B 1 1 = 1 0 1 = 0 1 0 = 0 0 0 = 1
Последствия
Символ в логике = ›или« если а, то б »
Символ в электронике Нет
Что он делает. Если A верно, то B также верно
Таблица истинности
Истина под толкованием
Учитывая интерпретацию I, мы можем вычислить значение истинности любой формулы P относительно I. То есть, имея версию формулы, мы можем вычислить значение истинности.
если I (P) = 1, то мы говорим, что P истинно при интерпретации I. Если I (P) = 0, то мы говорим, что P ложно при интерпретации I.
Логические головоломки
Этот раздел может помочь читателю разобраться в логических головоломках.
На острове есть два типа жителей: рыцари, которые всегда говорят правду, и лжецы, которые всегда лгут. Вы идете на остров и встречаетесь с A и B. A говорит, что «B - рыцарь» B говорит, что «мы двое - противоположные типы»
Что такое А и Б?
Итак, у нас есть 2 варианта, p: «A - рыцарь»; и q: «B - рыцарь»
У нас есть 2 варианта, потому что один из них должен быть рыцарем. Либо и A, и B - лжецы, что делает B рыцарем, поскольку он сказал правду, поэтому он солгал, либо A - рыцарь и говорит правду, что B - рыцарь.
Варианты для человека A p истинно, то есть утверждение «A - рыцарь» верно. P = ›Q p ложно, то есть утверждение« A - рыцарь »неверно. ¬P = ›¬Q
Параметры для человека B q истинно, тогда q = ›¬p q ложно, тогда ¬q =› ¬p
Теперь нам просто нужно построить таблицу истинности для этих значений.
p q ¬p ¬q p => q ¬p => ¬q q => ¬p ¬q => ¬p 0 0 1 1 1 1 1 1 = 1
Затем мы останавливаемся на этом, потому что мы нашли приемлемую интерпретацию, согласно которой они оба являются лжецами.
Семантическое следствие
Примечание. Слайды лекции для этого не помогли, и для этого нет звука. Пожалуйста, напишите мне, что это такое.
Цифровые логические схемы
Современные компьютеры используют для работы логические вентили. Вы должны иметь представление о логических воротах из вышеизложенного.
Общие правила оформления электрических цепей
Никогда не совмещайте два входных провода
Если есть 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
Ассиокационный закон
а (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/]
Неверные правила
Не Не А = А А или А и В = А А или нет А и В = А и В (А или В) (А или С) = А или В и С.
Что делать дальше. С этого момента превратите схему в логическое выражение и упростите его, используя приведенные выше правила.
Если это все еще сбивает с толку, возможно, вам поможет это видео: https://www.youtube.com/watch?v=59BbncMjL8I
Булевы функции
Арность. Арность логической функции - это количество аргументов, которые она принимает.
Представление логической функции
Любое логическое значение может быть представлено с помощью ^, v или ¬.
Логические ворота расширены
В этом разделе мы еще немного рассмотрим логические ворота, рассмотрев семейство неэксклюзивных ворот.
XOR
Символ в логике
Никто
Символ в электронике
Что он делает
Элемент XOR принимает ›1 вход и выполняет исключительную дизъюнкцию. Выход элемента XOR истинен только в том случае, если один из его входов отличается от другого входа.
Таблица истинности
NAND
Символ в логике
Никто
Символ в электронике
Что он делает
Логический элемент И-НЕ принимает ›1 вход, а выход является противоположным логическому элементу И. Выходные данные являются истинными, когда один или несколько, но не все его входные данные являются ложными.
Таблица истинности
Универсальность XOR и NAND
Все логические функции могут быть созданы с использованием вентилей 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
Зная эти основные правила, вы можете складывать любые числа в двоичном формате так же, как и обычные числа. Попробуйте это упражнение
011
полусумматор
Полусумматор - это тип двоичного сумматора в электронике, который складывает две одиночные двоичные цифры и обеспечивает вывод плюс значение переноса.
Примечание: полусумматор Бориса слишком сложен, вы можете добиться того же, заменив 3 его логических элемента одним элементом XOR.
Таблица правды
Полный сумматор
Полный сумматор позволяет выполнять как перенос, так и вынос.
Посмотрите это видео, чтобы лучше понять
Https://www.youtube.com/watch?v=VPw9vPN-3ac
Обозначение черного ящика
Мы можем представить полный сумматор в виде черного ящика, нам не нужно знать, что внутри него происходит, только входы и выходы.
4-битный сумматор
Используя нотацию черного ящика, мы можем создать 4-битный сумматор
Http://www.electronics-tutorials.ws/combination/comb_7.html
Компьютерное представление отрицательных целых чисел
Для представления целых чисел используется фиксированное количество бит: 8, 16, 32 или 64 бита. Целое число без знака может занимать все доступное пространство.
Вы можете «подписать» двоичное число, чтобы указать, отрицательное оно или нет. Например, число 10 может быть представлено в 8-битном формате как 00001010, а -10 может быть представлено в 8-битном формате как 10001010.
Но это иногда вызывает проблемы, например, 10000000 представляет -0. Whaaatt ?? Отрицательный 0? Да! Это верно, и это именно та проблема, которую это вызывает.
Здесь в игру вступает дополнение 2.
Дополнение до двоек
Преобразование десятичной дроби в двоичное дополнение
1) Преобразуйте число в двоичное, пока не обращайте внимания на знак. Итак, 5 - это 0101, а -5 - это 0101.
2) Если число положительное, то все готово, дальше идти не нужно. Иначе…
3) Если число отрицательное, то:
- Найдите дополнение (например, преобразуйте все 0 в 1 и все 1 в 0)
- Добавьте 1 к дополнению
Итак, инвертируем все цифры и прибавляем 1. Просто.
Если вы хотите узнать, почему это работает, нажмите здесь
Дополнение в двоичном формате, пересмотрено
Перенос, который срывается с конца, часто можно игнорировать, например:
-1 + -3 1111
- 1101 1100 с переносом 1, идущим влево, его можно игнорировать.
Вычитание в двоичном формате
Считайте это сложением, но игнорируйте второй операнд. Итак, 4–3 - это всего лишь 4 + (-3)
Это просто
0100
Переполнение
Примером этого является 4 + 7
0100
Правильный результат 9 слишком велик, чтобы уместиться в 4-битном представлении.
Если оба входа в добавлении имеют одинаковый знак, а выходной знак разный, произошло переполнение.
Переполнение не может произойти, если признаки различаются.
Первоначально опубликовано на сайте brandonskerritt.github.io 25 ноября 2017 г.
