Following up on my previous post about truth tables, I now ask a subtler question: which inputs actually matter? Some variables, though present, leave no trace on the output. In this post, I uncover those quiet bits — the irrelevant inputs — and learn how to spot them with precision.
Building on the previous
The previous post showed that for a given number of inputs, there is a finite, but rapidly growing, number of possible truth tables. For two inputs, there are 16. For three inputs, there are 256. This leads to a powerful idea: we can create a standardized format for all truth tables and uniquely identify the parts in each one.
The Standardized Truth Table (STT) Format
i[1] i[0] : r
=================
0 0 : 0
0 1 : 0
1 0 : 0
1 1 : 1
Colour Key
- Inputs
- Input count
- Result, r
- Result vector: 0001
We have a standardized truth table with inputs. Each row in the inputs section of the truth table is an increasing binary count from to . The result column for the truth table has rows, leading to different possible truth table result vectors for inputs.
Any one possible result, , of the standardized truth table is read as the binary bits of the output going from the topmost row (where the inputs are all zero) down to the bottom-most row, in order. This single binary number, the "result number" or vector, uniquely identifies the truth table and the boolean function it represents.
Irrelevant Variables in Boolean Expressions
A variable in a boolean expression is considered irrelevant if its value has no effect on the final output. In a truth table, this means that changing the value of that input variable while all other inputs remain the same does not change the output.
While this is easy to understand, it can be difficult to spot for complex functions. This is where the standardized truth table format, STT, comes in handy.
Irrelevancy Calculation
For an -input truth table with a bit result, , we can efficiently check for irrelevant variables. The key insight is that for any single input variable, say , the other input bits change in the exact same order when as they do when , in the input count region of the STT.
Therefore, if the result bits for the rows where are the same as the result bits for the rows where , then the input variable has no effect on the output and is therefore irrelevant.
Let's illustrate with an example for a 3-input truth table.
Example
| i[2] | i[1] | i[0] | : | Output |
|---|---|---|---|---|
| 0 | 0 | 0 | : | r0 |
| 0 | 0 | 1 | : | r1 |
| 0 | 1 | 0 | : | r2 |
| 0 | 1 | 1 | : | r3 |
| 1 | 0 | 0 | : | r4 |
| 1 | 0 | 1 | : | r5 |
| 1 | 1 | 0 | : | r6 |
| 1 | 1 | 1 | : | r7 |
Consider checking if is irrelevant. The values of the other inputs ( and ) follow the sequence 00, 01, 10, 11 both when is 0 and when is 1.
When , the corresponding output bits are .
When , the corresponding output bits are .
If the sequence of bits is identical to the sequence of bits , then the input variable has no effect on the output and is therefore irrelevant.
This method allows for a very efficient, algorithmic approach to simplifying boolean expressions.
from collections import defaultdict
import pprint
def is_irrelevant(considered: int,
input_count:int,
result_vector: int) -> bool:
"""
Determine whether a specific input variable is irrelevant to the output of the truth table.
Args:
considered: Index of the input variable to test.
input_count: Total number of input variables.
result_vector: Integer representing the output bits of the truth table.
Returns:
True if the input is irrelevant, False otherwise.
"""
considered_to_resultbits = {0: [], 1: []}
for in_count in range(2**input_count):
considered_bit = (in_count >> considered) & 1
resultbit = (result_vector >> in_count) & 1
considered_to_resultbits[considered_bit].append(resultbit)
return considered_to_resultbits[0] == considered_to_resultbits[1]
def find_irrelevant_ttable_inputs(input_count:int,
result_vector: int) -> list[int]:
"""
Identify which input variables are irrelevant in a standardized truth table.
Args:
input_count: Number of input variables.
result_vector: Integer representing the output bits of the truth table.
Returns:
List of input indices that are irrelevant.
"""
irrelevant = [i for i in range(input_count)
if is_irrelevant(i, input_count, result_vector)]
return irrelevant
Relevant and irrelevant result vectors for STT's
I am interested in the truthtables/boolean expressions of an increasing number of inputs. Previousely I was taking all the zero input STT, then all the 1-input, all the 2-input, ...
That had repettitions and irrelevancies. I can now take just the relevant result vectors for each case, or, take the maximum inputs I canhandle and sort the result vectors so that those with the most irrelevancies for that maximum number of inputs, come first.
Here's the code I used to investigate these properties of irrelevances:
def print_STT_results_sensitive_to_inputs(max_input_count: int) -> None:
"""
Print a summary of irrelevance patterns across all standardized truth tables (STTs)
for input counts from 0 up to `max_input_count - 1`.
For each input count `i`, the function:
- Computes all possible result vectors (2**(2**i))
- Identifies which inputs are irrelevant for each result
- Summarizes how many result vectors have at least one irrelevant input
- Prints spacing patterns (diffs) between result indices with irrelevance
- Checks whether irrelevance indices for input count `i` begin with those from `i-1`
Args:
max_input_count: The exclusive upper bound on input counts to analyze.
"""
imax2irrelevances = {}
for imax in range(max_input_count):
print(f"\nINPUTS = {imax}\n==========")
result_count = 2**2**imax
print(f" total_possible_tt_results =", result_count)
result2irrelevances = {r:[i for i in range(imax)
if is_irrelevant(i, imax, r)]
for r in range(result_count)}
txt = pprint.pformat(result2irrelevances, compact=True, indent=2).replace('\n', '\n ')
txt = txt.replace('{', '{\n ')
#print(" result2irrelevances = ", txt)
irrelevances = [k for k, v in result2irrelevances.items()
if v]
imax2irrelevances[imax] = irrelevances
relevances = result_count - len(irrelevances)
print(f" {irrelevances = }")
print(f" {len(irrelevances) = }, {relevances = }")
table = chop_line(format_irrelevance_table_full(result2irrelevances, imax)[0], 220)
print("\nSTT Result Irrelevance vs Input Table"
f"\n{table}")
# First-order differences between irrelevance indices
diff0 = [irrelevances[j] - irrelevances[j-1]
for j in range(1, len(irrelevances))]
#print(f" {diff0 = }")
# Second-order differences between irrelevance indices
diff1 = [diff0[j] - diff0[j-1]
for j in range(1, len(diff0))]
#print(f" {diff1 = }")
print("\n\nIrrelevance indices reflected about the center of the r count?"
f"\n {is_irrelevance_reflected(imax2irrelevances)}") # True so far
print('Irrelevances for `i` inputs begin with those from `i-1`?')
previous_prefixed = all((i0 := imax2irrelevances[i-1]) == imax2irrelevances[i][:len(i0)]
for i in range(1, max_input_count))
print(f" {previous_prefixed}") # True so far
def is_irrelevance_reflected(ins2irrel: dict[int, list[int]]) -> bool:
"""
Check whether irrelevance indices are symmetric about the center of the result vector space.
For each input count `i`, the result vector space has size 2**(2**i).
This function checks whether for every irrelevance index `r < half_range`,
its mirror index `full_range - 1 - r` is also marked as irrelevant.
Args:
ins2irrel: Mapping from input count to list of result indices with irrelevance.
Returns:
True if all irrelevance sets are symmetric about the center, False otherwise.
"""
for imax, irrelevances in ins2irrel.items():
irrel_set = set(irrelevances)
full_range = 2**2**imax
half_range = full_range / 2
if not all((full_range - 1 - i) in irrel_set for i in irrel_set if i < half_range):
return False
return True
def format_irrelevance_table(result2irrelevances: dict[int, list[int]], input_count: int) -> tuple[str, str]:
"""
Create a compact table showing which inputs are irrelevant for each result vector `r`.
Each column is sized to match the width of its corresponding `r` value.
Only includes columns for `r` values that have at least one irrelevant input.
Each row corresponds to an input index, with '@' if that input is irrelevant for that `r`, else blank.
Returns:
A tuple of (plain text table string, markdown table string)
"""
if input_count == 0:
msg = "No inputs to analyze (input_count = 0)."
md = "| Input | (none) |\n|-------|--------|\n| (none) | |"
return msg, md
filtered_r = [r for r, irrels in result2irrelevances.items() if irrels]
if not filtered_r:
msg = "No irrelevant inputs found for any result vector."
md = "| Input | (none) |\n|-------|--------|\n" + "\n".join(
f"| i[{i}] | |" for i in range(input_count)
)
return msg, md
# Determine individual column widths based on r string length
r_labels = [str(r) for r in filtered_r]
col_widths = [len(label) for label in r_labels]
# Header row
header_plain = " " * 8 + " ".join(label.rjust(w) for label, w in zip(r_labels, col_widths))
header_md = "| Input | " + " | ".join(label.rjust(w) for label, w in zip(r_labels, col_widths)) + " |"
# Markdown separator row
separator_md = "|-------|" + "|".join("-" * (w + 2) for w in col_widths) + "|"
# Rows
rows_plain = []
rows_md = []
for i in range(input_count):
label = f"i[{i}]".ljust(8)
row_plain = label + " ".join("@" .rjust(w) if i in result2irrelevances[r] else " " * w
for r, w in zip(filtered_r, col_widths))
row_md = "| " + f"i[{i}]".ljust(5) + " | " + " | ".join("@" .rjust(w) if i in result2irrelevances[r] else " " * w
for r, w in zip(filtered_r, col_widths)) + " |"
rows_plain.append(row_plain)
rows_md.append(row_md)
plain_table = "\n".join([header_plain] + rows_plain)
markdown_table = "\n".join([header_md, separator_md] + rows_md)
return plain_table, markdown_table
def format_irrelevance_table_full(result2irrelevances: dict[int, list[int]], input_count: int) -> tuple[str, str]:
"""
Create a full table showing which inputs are irrelevant for each result vector `r`.
Includes columns for all result vector indices (0 to max(r)).
Each row corresponds to an input index, with '@' if that input is irrelevant for that `r`, else blank.
Returns:
A tuple of (plain text table string, markdown table string)
"""
if input_count == 0:
msg = "No inputs to analyze (input_count = 0)."
md = "| Input | (none) |\n|-------|--------|\n| (none) | |"
return msg, md
all_r = sorted(result2irrelevances.keys())
r_labels = [str(r) for r in all_r]
col_widths = [len(label) for label in r_labels]
# Header row
header_plain = " " * 8 + " ".join(label.rjust(w) for label, w in zip(r_labels, col_widths))
header_md = "| Input | " + " | ".join(label.rjust(w) for label, w in zip(r_labels, col_widths)) + " |"
# Markdown separator row
separator_md = "|-------|" + "|".join("-" * (w + 2) for w in col_widths) + "|"
# Rows
rows_plain = []
rows_md = []
for i in range(input_count):
label = f"i[{i}]".ljust(8)
row_plain = label + " ".join("@" .rjust(w) if i in result2irrelevances.get(r, []) else " " * w
for r, w in zip(all_r, col_widths))
row_md = "| " + f"i[{i}]".ljust(5) + " | " + " | ".join("@" .rjust(w) if i in result2irrelevances.get(r, []) else " " * w
for r, w in zip(all_r, col_widths)) + " |"
rows_plain.append(row_plain)
rows_md.append(row_md)
plain_table = "\n".join([header_plain] + rows_plain)
markdown_table = "\n".join([header_md, separator_md] + rows_md)
return plain_table, markdown_table
def chop_line(table_text: str, max_length: int) -> str:
"""
Chop each line in a multi-line string to a maximum length.
If a line exceeds `max_length`, it is truncated to `max_length - 3` and '...' is appended.
Args:
table_text: The full multi-line string to process.
max_length: The maximum allowed line length.
Returns:
A new multi-line string with long lines chopped and marked with '...'.
"""
chopped_lines = []
for line in table_text.splitlines():
if len(line) > max_length:
chopped_lines.append(line[:max_length - 3] + '...')
else:
chopped_lines.append(line)
return '\n'.join(chopped_lines)
print_STT_results_sensitive_to_inputs(5)
Irrelevances: Output
INPUTS = 0
==========
total_possible_tt_results = 2
irrelevances = []
len(irrelevances) = 0, relevances = 2
STT Result Irrelevance vs Input Table
No inputs to analyze (input_count = 0).
INPUTS = 1
==========
total_possible_tt_results = 4
irrelevances = [0, 3]
len(irrelevances) = 2, relevances = 2
STT Result Irrelevance vs Input Table
0 1 2 3
i[0] @ @
INPUTS = 2
==========
total_possible_tt_results = 16
irrelevances = [0, 3, 5, 10, 12, 15]
len(irrelevances) = 6, relevances = 10
STT Result Irrelevance vs Input Table
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
i[0] @ @ @ @
i[1] @ @ @ @
INPUTS = 3
==========
total_possible_tt_results = 256
irrelevances = [0, 3, 5, 10, 12, 15, 17, 34, 48, 51, 60, 63, 68, 80, 85, 90, 95, 102, 119, 136, 153, 160, 165, 170, 175, 187, 192, 195, 204, 207, 221, 238, 240, 243, 245, 250, 252, 255]
len(irrelevances) = 38, relevances = 218
STT Result Irrelevance vs Input Table
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 ...
i[0] @ @ @ @ @ @ @ @ ...
i[1] @ @ @ @ ...
i[2] @ @ @ @ @ ...
INPUTS = 4
==========
total_possible_tt_results = 65536
irrelevances = [0, 3, 5, 10, 12, 15, 17, 34, 48, 51, 60, 63, 68, 80, 85, 90, 95, 102, 119, 136, 153, 160, 165, 170, 175, 187, 192, 195, 204, 207, 221, 238, 240, 243, 245, 250, 252, 255, 257, 514, 768, 771, 780, 783, 816, 819, 828, 831, 960, 963, 972, 975, 1008, 1011, 1020, 1023, 1028, 1280, 1285, 1290, 1295, 1360, 1365, 1370, 1375, 1440, 1445, 1450, 1455, 1520, 1525, 1530, 1535, 1542, 1799, 2056, 2313, 2560, 2565, 2570, 2575, 2640, 2645, 2650, 2655, 2720, 2725, 2730, 2735, 2800, 2805, 2810, 2815, 2827, 3072, 3075, 3084, 3087, 3120, 3123, 3132, 3135, 3264, 3267, 3276, 3279, 3312, 3315, 3324, 3327, 3341, 3598, 3840, 3843, 3845, 3850, 3852, 3855, 3888, 3891, 3900, 3903, 3920, 3925, 3930, 3935, 4000, 4005, 4010, 4015, 4032, 4035, 4044, 4047, 4080, 4083, 4085, 4090, 4092, 4095, 4112, 4352, 4369, 4386, 4403, 4420, 4437, 4454, 4471, 4488, 4505, 4522, 4539, 4556, 4573, 4590, 4607, 4626, 4883, 5140, 5397, 5654, 5911, 6168, 6425, 6682, 6939, 7196, 7453, 7710, 7967, 8224, 8481, 8704, 8721, 8738, 8755, 8772, 8789, 8806, 8823, 8840, 8857, 8874, 8891, 8908, 8925, 8942, 8959, 8995, 9252, 9509, 9766, 10023, 10280, 10537, 10794, 11051, 11308, 11565, 11822, 12079, 12288, 12291, 12300, 12303, 12336, 12339, 12348, 12351, 12480, 12483, 12492, 12495, 12528, 12531, 12540, 12543, 12593, 12850, 13056, 13059, 13068, 13071, 13073, 13090, 13104, 13107, 13116, 13119, 13124, 13141, 13158, 13175, 13192, 13209, 13226, 13243, 13248, 13251, 13260, 13263, 13277, 13294, 13296, 13299, 13308, 13311, 13364, 13621, 13878, 14135, 14392, 14649, 14906, 15163, 15360, 15363, 15372, 15375, 15408, 15411, 15420, 15423, 15552, 15555, 15564, 15567, 15600, 15603, 15612, 15615, 15677, 15934, 16128, 16131, 16140, 16143, 16176, 16179, 16188, 16191, 16320, 16323, 16332, 16335, 16368, 16371, 16380, 16383, 16448, 16705, 16962, 17219, 17408, 17425, 17442, 17459, 17476, 17493, 17510, 17527, 17544, 17561, 17578, 17595, 17612, 17629, 17646, 17663, 17733, 17990, 18247, 18504, 18761, 19018, 19275, 19532, 19789, 20046, 20303, 20480, 20485, 20490, 20495, 20560, 20565, 20570, 20575, 20640, 20645, 20650, 20655, 20720, 20725, 20730, 20735, 20817, 21074, 21331, 21588, 21760, 21765, 21770, 21775, 21777, 21794, 21811, 21828, 21840, 21845, 21850, 21855, 21862, 21879, 21896, 21913, 21920, 21925, 21930, 21935, 21947, 21964, 21981, 21998, 22000, 22005, 22010, 22015, 22102, 22359, 22616, 22873, 23040, 23045, 23050, 23055, 23120, 23125, 23130, 23135, 23200, 23205, 23210, 23215, 23280, 23285, 23290, 23295, 23387, 23644, 23901, 24158, 24320, 24325, 24330, 24335, 24400, 24405, 24410, 24415, 24480, 24485, 24490, 24495, 24560, 24565, 24570, 24575, 24672, 24929, 25186, 25443, 25700, 25957, 26112, 26129, 26146, 26163, 26180, 26197, 26214, 26231, 26248, 26265, 26282, 26299, 26316, 26333, 26350, 26367, 26471, 26728, 26985, 27242, 27499, 27756, 28013, 28270, 28527, 28784, 29041, 29298, 29555, 29812, 30069, 30326, 30464, 30481, 30498, 30515, 30532, 30549, 30566, 30583, 30600, 30617, 30634, 30651, 30668, 30685, 30702, 30719, 30840, 31097, 31354, 31611, 31868, 32125, 32382, 32639, 32896, 33153, 33410, 33667, 33924, 34181, 34438, 34695, 34816, 34833, 34850, 34867, 34884, 34901, 34918, 34935, 34952, 34969, 34986, 35003, 35020, 35037, 35054, 35071, 35209, 35466, 35723, 35980, 36237, 36494, 36751, 37008, 37265, 37522, 37779, 38036, 38293, 38550, 38807, 39064, 39168, 39185, 39202, 39219, 39236, 39253, 39270, 39287, 39304, 39321, 39338, 39355, 39372, 39389, 39406, 39423, 39578, 39835, 40092, 40349, 40606, 40863, 40960, 40965, 40970, 40975, 41040, 41045, 41050, 41055, 41120, 41125, 41130, 41135, 41200, 41205, 41210, 41215, 41377, 41634, 41891, 42148, 42240, 42245, 42250, 42255, 42320, 42325, 42330, 42335, 42400, 42405, 42410, 42415, 42480, 42485, 42490, 42495, 42662, 42919, 43176, 43433, 43520, 43525, 43530, 43535, 43537, 43554, 43571, 43588, 43600, 43605, 43610, 43615, 43622, 43639, 43656, 43673, 43680, 43685, 43690, 43695, 43707, 43724, 43741, 43758, 43760, 43765, 43770, 43775, 43947, 44204, 44461, 44718, 44800, 44805, 44810, 44815, 44880, 44885, 44890, 44895, 44960, 44965, 44970, 44975, 45040, 45045, 45050, 45055, 45232, 45489, 45746, 46003, 46260, 46517, 46774, 47031, 47288, 47545, 47802, 47872, 47889, 47906, 47923, 47940, 47957, 47974, 47991, 48008, 48025, 48042, 48059, 48076, 48093, 48110, 48127, 48316, 48573, 48830, 49087, 49152, 49155, 49164, 49167, 49200, 49203, 49212, 49215, 49344, 49347, 49356, 49359, 49392, 49395, 49404, 49407, 49601, 49858, 49920, 49923, 49932, 49935, 49968, 49971, 49980, 49983, 50112, 50115, 50124, 50127, 50160, 50163, 50172, 50175, 50372, 50629, 50886, 51143, 51400, 51657, 51914, 52171, 52224, 52227, 52236, 52239, 52241, 52258, 52272, 52275, 52284, 52287, 52292, 52309, 52326, 52343, 52360, 52377, 52394, 52411, 52416, 52419, 52428, 52431, 52445, 52462, 52464, 52467, 52476, 52479, 52685, 52942, 52992, 52995, 53004, 53007, 53040, 53043, 53052, 53055, 53184, 53187, 53196, 53199, 53232, 53235, 53244, 53247, 53456, 53713, 53970, 54227, 54484, 54741, 54998, 55255, 55512, 55769, 56026, 56283, 56540, 56576, 56593, 56610, 56627, 56644, 56661, 56678, 56695, 56712, 56729, 56746, 56763, 56780, 56797, 56814, 56831, 57054, 57311, 57568, 57825, 58082, 58339, 58596, 58853, 59110, 59367, 59624, 59881, 60138, 60395, 60652, 60909, 60928, 60945, 60962, 60979, 60996, 61013, 61030, 61047, 61064, 61081, 61098, 61115, 61132, 61149, 61166, 61183, 61423, 61440, 61443, 61445, 61450, 61452, 61455, 61488, 61491, 61500, 61503, 61520, 61525, 61530, 61535, 61600, 61605, 61610, 61615, 61632, 61635, 61644, 61647, 61680, 61683, 61685, 61690, 61692, 61695, 61937, 62194, 62208, 62211, 62220, 62223, 62256, 62259, 62268, 62271, 62400, 62403, 62412, 62415, 62448, 62451, 62460, 62463, 62708, 62720, 62725, 62730, 62735, 62800, 62805, 62810, 62815, 62880, 62885, 62890, 62895, 62960, 62965, 62970, 62975, 63222, 63479, 63736, 63993, 64000, 64005, 64010, 64015, 64080, 64085, 64090, 64095, 64160, 64165, 64170, 64175, 64240, 64245, 64250, 64255, 64507, 64512, 64515, 64524, 64527, 64560, 64563, 64572, 64575, 64704, 64707, 64716, 64719, 64752, 64755, 64764, 64767, 65021, 65278, 65280, 65283, 65285, 65290, 65292, 65295, 65297, 65314, 65328, 65331, 65340, 65343, 65348, 65360, 65365, 65370, 65375, 65382, 65399, 65416, 65433, 65440, 65445, 65450, 65455, 65467, 65472, 65475, 65484, 65487, 65501, 65518, 65520, 65523, 65525, 65530, 65532, 65535]
len(irrelevances) = 942, relevances = 64594
STT Result Irrelevance vs Input Table
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 ...
i[0] @ @ @ @ @ @ @ @ ...
i[1] @ @ @ @ ...
i[2] @ @ @ @ @ ...
i[3] @ ...
Irrelevance indices reflected about the center of the r count?
True
Irrelevances for `i` inputs begin with those from `i-1`?
True
OEIS
The sequence of relevances: 2, 2, 10, 218, 64594 is already present as A000371 on OEIS.
The sequences of irelevances: 0, 2, 6, 38, 942 had no exact match although A005530 came close
END.
No comments:
Post a Comment