Количество логических операций
Количество логических операций — это число знаков логических действий в формуле. Подсчёт нужен, чтобы оценить сложность выражения и понять, сколько действий потребуется выполнить при вычислении его значения.
Сначала полезно вспомнить, что такое формула логики и какие знаки обозначают логические операции. Переменные, константы, скобки и знаки сравнения сами по себе логическими операциями не являются. Отрицание считается одной операцией и относится только к следующей переменной или заключённому в скобки выражению.
Как считать
- Найти все знаки логических операций в формуле.
- Посчитать каждое вхождение знака отдельно.
- Не считать переменные, константы и скобки.
- При необходимости определить порядок выполнения по приоритету логических операций.
Здесь \(N\) — общее количество операций, а \(N_{\neg}\), \(N_{\land}\) и другие величины — количество операций каждого вида. Формула означает обычный подсчёт всех знаков действий, а не число шагов в записи решения.
В выражении \(\neg A \lor (B \land C) \rightarrow D\) четыре операции: одно отрицание, одна конъюнкция, одна дизъюнкция и одна импликация. Следовательно, \(N=4\). Скобки и четыре переменные в подсчёт не входят.
Количество операций не равно количеству переменных и не всегда равно числу строк или шагов вычисления. Например, в выражении \(A \lor A\) две переменные записаны одинаково, но операция только одна — дизъюнкция. Повторное вхождение переменной само по себе новой операцией не становится.
Сколько логических операций в выражении \((A \land B) \lor \neg C\)?
Главное
- Считайте каждое вхождение знака логической операции.
- Отрицание, конъюнкция, дизъюнкция и импликация считаются отдельными операциями.
- Переменные, константы и скобки в количество операций не входят.