Известно, что с помощью штриха Шеффера (отрицание конъюнкции) можно выразить любую булеву функцию. Таблица истинности штриха Шеффера приведена ниже: Рассмотрим задачу сложения двух двоичных чисел и , каждое из которых состоит из бит. Биты в числах и

Добавлена: 30.04.2026
Обновлена: 30.04.2026
Предмет: Логика
Автор: Кэмп

#Символическая логика
#Математическая логика

Условие:

Известно, что с помощью штриха Шеффера (отрицание конъюнкции) можно выразить любую булеву функцию. Таблица истинности штриха Шеффера приведена ниже:

\begin{array}{|c|c|c|} \hline $x$ & $y$ & $x \mid y$ \\ \hline 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \hline \end{array}

Рассмотрим задачу сложения двух двоичных чисел $A$ и $B$ , каждое из которых состоит из $N$ бит. Биты в числах $A$ и $B$ пронумерованы от 0 (младший разряд) до $N-1$ (старший разряд). Сумму $A$ и $B$ всегда можно представить как $N+1$ -битное число. Назовем самый старший бит суммы (бит с номером $N$ ) битом переполнения.

Вам нужно построить булеву формулу, вычисляющую значение бита переполнения для произвольных $N$ -битных чисел $A$ и $B$ , используя только штрих Шеффера. Формула строится по следующим правилам:

Аі - формула, равная значению $i$ -го бита числа $A$ .
Ві - формула, равная значению $i$ -го бита числа $B$ .
(x|y) - формула, обозначающая применение штриха Шеффера к $x$ и $y$ , где $x$ и $y$ - некоторые формулы.

Индекс $i$ в формулах для битов чисел $A$ и $B$ записывайте десятичным числом без ведущих нулей, например, бит числа $A$ с номером 12 должен быть записан как А12. Вокруг каждого применения штриха Шеффера должны стоять скобки (согласно третьему правилу). Внутри формулы не должно быть пробелов. Вход содержит число $N(1 \leqslant N \leqslant 100)$ . Выведите формулу, вычисляющую бит переполнения суммы двух $N$ -битных чисел $A$ и $B$ по правилам, описанным в условии. Для обозначения штриха Шеффера используйте символ I (ASCII код 124).

Размер выходного файла не должен превосходить $50 N$ байт.

Решение:

Нам нужно получить булеву функцию, которая по N‑битным числам A и B (с битами A0,…,A(N–1) и B0,…,B(N–1)) вычисляет бит переполнения суммы, то есть бит Cₙ, если определить перенос по разрядам следующим образом:

c₀ = 0,
cᵢ₊₁ = (Aᵢ ∧ Bᵢ) ∨ ((Aᵢ ∨ Bᵢ) ∧ cᵢ) для i = 0,…,N–1.

При этом сумма равна S = ∑₍ᵢ₌₀₎ⁿ₁ (Aᵢ ⊕ Bᵢ ⊕ cᵢ)·2ᶦ и бит переполнения – это cₙ.

Далее воспользуемся известным фактом, что штрих Шеффера (операция NAND, обозначаемая символом I) является функционально полным. Именно, можно получить следующие основные логические операции (кажд...