Теория
Логическая схема собирается из вентилей — базовых элементов, которые выполняют операции алгебры логики. Вентиль И (конъюнкция) даёт 1 только тогда, когда все его входы равны 1; вентиль ИЛИ (дизъюнкция) — когда хотя бы один вход равен 1; вентиль НЕ (отрицание) переворачивает значение. Схема с одним выходом \(F\) задаёт логическую функцию от входов \(A\), \(B\), \(C\), \(D\).
Чтобы найти функцию схемы, каждый вентиль записывают выражением: входы подставляют в операцию, а результат получает имя. Схема читается сверху вниз: вентиль может использовать только входы и вентили, описанные выше. Например, запись u1 = И(A, B), u2 = НЕ(C), F = ИЛИ(u1, u2) даёт функцию \(F = (A \wedge B) \vee \neg C\). Дальше её исследуют как обычное выражение: по таблице истинности видно, на каких наборах \(F = 1\), и является ли функция тождественно истинной, тождественно ложной или выполнимой.
Важно: порядок строк в записи схемы — это порядок вычисления. Вентиль, описанный ниже, в выражении выше использовать нельзя; поэтому в схеме не бывает циклов.
Пример с решением
- Условие. Дана схема:
u1 = И(A, B),u2 = НЕ(C),F = ИЛИ(u1, u2). Найти функцию и её таблицу истинности. - Формулы. \(u\_1 = A \wedge B\), \(u\_2 = \neg C\), \(F = u\_1 \vee u\_2\).
- Подстановка. \(F = (A \wedge B) \vee \neg C\).
- Вычисление. При \(A = 1\), \(B = 1\), \(C = 0\): \(u_1 = 1\), \(u_2 = 1\), \(F = 1\). При \(A = 1\), \(B = 0\), \(C = 0\): \(u_1 = 0\), \(u_2 = 1\), \(F = 1\). Полная таблица из восьми строк даёт \(F = 1\) на пяти наборах.
- Ответ. \(F = (A \wedge B) \vee \neg C\); функция выполнимая, \(F = 1\) на 5 наборах из 8. Калькулятор с этой схемой выдаёт ту же функцию и ту же таблицу.
Главное
- Вентили: И — все входы 1; ИЛИ — хотя бы один вход 1; НЕ — инверсия входа.
- Запись схемы: одна строка — один вентиль; ссылаться можно на входы A–D и на вентили, описанные выше.
- Выход обозначается F; по схеме собирается выражение, по выражению — таблица истинности.
- Тип функции: тождественно истинная, тождественно ложная или выполнимая.