problemreductions/
truth_table.rs

1//! Truth table utilities for logic gadgets.
2//!
3//! This module provides a `TruthTable` type for representing boolean functions
4//! and their truth tables, useful for constructing logic gadgets in reductions.
5
6use bitvec::prelude::*;
7use serde::{Deserialize, Serialize};
8
9/// A truth table representing a boolean function.
10///
11/// The truth table stores the output for each possible input combination.
12/// For n input variables, there are 2^n rows in the table.
13///
14/// # Example
15///
16/// ```
17/// use problemreductions::truth_table::TruthTable;
18///
19/// // Create AND gate truth table
20/// let and_gate = TruthTable::from_outputs(2, vec![false, false, false, true]);
21/// assert!(!and_gate.evaluate(&[false, false]));
22/// assert!(!and_gate.evaluate(&[true, false]));
23/// assert!(and_gate.evaluate(&[true, true]));
24/// ```
25#[derive(Debug, Clone, PartialEq, Eq)]
26pub struct TruthTable {
27    /// Number of input variables.
28    num_inputs: usize,
29    /// Output values for each input combination.
30    /// Index corresponds to input as binary number (LSB first).
31    outputs: BitVec,
32}
33
34/// Serialization-friendly representation of a TruthTable.
35#[derive(Serialize, Deserialize)]
36struct TruthTableSerde {
37    num_inputs: usize,
38    outputs: Vec<bool>,
39}
40
41impl Serialize for TruthTable {
42    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
43    where
44        S: serde::Serializer,
45    {
46        let serde_repr = TruthTableSerde {
47            num_inputs: self.num_inputs,
48            outputs: self.outputs.iter().by_vals().collect(),
49        };
50        serde_repr.serialize(serializer)
51    }
52}
53
54impl<'de> Deserialize<'de> for TruthTable {
55    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
56    where
57        D: serde::Deserializer<'de>,
58    {
59        let serde_repr = TruthTableSerde::deserialize(deserializer)?;
60        Ok(TruthTable {
61            num_inputs: serde_repr.num_inputs,
62            outputs: serde_repr.outputs.into_iter().collect(),
63        })
64    }
65}
66
67impl TruthTable {
68    /// Create a truth table from a vector of boolean outputs.
69    ///
70    /// The outputs vector must have exactly 2^num_inputs elements.
71    /// Index i corresponds to the input where the j-th bit represents variable j.
72    pub fn from_outputs(num_inputs: usize, outputs: Vec<bool>) -> Self {
73        let expected_len = 1 << num_inputs;
74        assert_eq!(
75            outputs.len(),
76            expected_len,
77            "outputs length must be 2^num_inputs = {}, got {}",
78            expected_len,
79            outputs.len()
80        );
81
82        let bits: BitVec = outputs.into_iter().collect();
83        Self { num_inputs, outputs: bits }
84    }
85
86    /// Create a truth table from a function.
87    ///
88    /// The function takes a slice of booleans (the input) and returns the output.
89    pub fn from_function<F>(num_inputs: usize, f: F) -> Self
90    where
91        F: Fn(&[bool]) -> bool,
92    {
93        let num_rows = 1 << num_inputs;
94        let mut outputs = BitVec::with_capacity(num_rows);
95
96        for i in 0..num_rows {
97            let input: Vec<bool> = (0..num_inputs).map(|j| (i >> j) & 1 == 1).collect();
98            outputs.push(f(&input));
99        }
100
101        Self { num_inputs, outputs }
102    }
103
104    /// Get the number of input variables.
105    pub fn num_inputs(&self) -> usize {
106        self.num_inputs
107    }
108
109    /// Get the number of rows (2^num_inputs).
110    pub fn num_rows(&self) -> usize {
111        1 << self.num_inputs
112    }
113
114    /// Evaluate the truth table for a given input.
115    pub fn evaluate(&self, input: &[bool]) -> bool {
116        assert_eq!(
117            input.len(),
118            self.num_inputs,
119            "input length must match num_inputs"
120        );
121
122        let index = Self::input_to_index(input);
123        self.outputs[index]
124    }
125
126    /// Evaluate using a usize config (0/1 values).
127    pub fn evaluate_config(&self, config: &[usize]) -> bool {
128        let input: Vec<bool> = config.iter().map(|&x| x != 0).collect();
129        self.evaluate(&input)
130    }
131
132    /// Convert an input to its index in the truth table.
133    fn input_to_index(input: &[bool]) -> usize {
134        input
135            .iter()
136            .enumerate()
137            .map(|(i, &b)| if b { 1 << i } else { 0 })
138            .sum()
139    }
140
141    /// Get the output values as a bitvec.
142    pub fn outputs(&self) -> &BitVec {
143        &self.outputs
144    }
145
146    /// Get all outputs as a vector of bools.
147    pub fn outputs_vec(&self) -> Vec<bool> {
148        self.outputs.iter().by_vals().collect()
149    }
150
151    /// Get the input configuration for a given row index.
152    pub fn index_to_input(&self, index: usize) -> Vec<bool> {
153        (0..self.num_inputs).map(|j| (index >> j) & 1 == 1).collect()
154    }
155
156    /// Count the number of true outputs.
157    pub fn count_ones(&self) -> usize {
158        self.outputs.count_ones()
159    }
160
161    /// Count the number of false outputs.
162    pub fn count_zeros(&self) -> usize {
163        self.outputs.count_zeros()
164    }
165
166    /// Check if the function is satisfiable (has at least one true output).
167    pub fn is_satisfiable(&self) -> bool {
168        self.outputs.any()
169    }
170
171    /// Check if the function is a tautology (all outputs are true).
172    pub fn is_tautology(&self) -> bool {
173        self.outputs.all()
174    }
175
176    /// Check if the function is a contradiction (all outputs are false).
177    pub fn is_contradiction(&self) -> bool {
178        self.outputs.not_any()
179    }
180
181    /// Get all satisfying assignments.
182    pub fn satisfying_assignments(&self) -> Vec<Vec<bool>> {
183        (0..self.num_rows())
184            .filter(|&i| self.outputs[i])
185            .map(|i| self.index_to_input(i))
186            .collect()
187    }
188
189    /// Create an AND gate truth table.
190    pub fn and(num_inputs: usize) -> Self {
191        Self::from_function(num_inputs, |input| input.iter().all(|&b| b))
192    }
193
194    /// Create an OR gate truth table.
195    pub fn or(num_inputs: usize) -> Self {
196        Self::from_function(num_inputs, |input| input.iter().any(|&b| b))
197    }
198
199    /// Create a NOT gate truth table (1 input).
200    pub fn not() -> Self {
201        Self::from_outputs(1, vec![true, false])
202    }
203
204    /// Create an XOR gate truth table.
205    pub fn xor(num_inputs: usize) -> Self {
206        Self::from_function(num_inputs, |input| {
207            input.iter().filter(|&&b| b).count() % 2 == 1
208        })
209    }
210
211    /// Create a NAND gate truth table.
212    pub fn nand(num_inputs: usize) -> Self {
213        Self::from_function(num_inputs, |input| !input.iter().all(|&b| b))
214    }
215
216    /// Create a NOR gate truth table.
217    pub fn nor(num_inputs: usize) -> Self {
218        Self::from_function(num_inputs, |input| !input.iter().any(|&b| b))
219    }
220
221    /// Create an XNOR gate truth table.
222    pub fn xnor(num_inputs: usize) -> Self {
223        Self::from_function(num_inputs, |input| {
224            input.iter().filter(|&&b| b).count() % 2 == 0
225        })
226    }
227
228    /// Create an implication gate (a -> b = !a OR b).
229    /// Input 0 is 'a', input 1 is 'b'.
230    pub fn implies() -> Self {
231        // Index 0: [F,F] -> T, Index 1: [T,F] -> F, Index 2: [F,T] -> T, Index 3: [T,T] -> T
232        Self::from_outputs(2, vec![true, false, true, true])
233    }
234
235    /// Combine two truth tables using AND.
236    pub fn and_with(&self, other: &TruthTable) -> TruthTable {
237        assert_eq!(self.num_inputs, other.num_inputs);
238        let outputs: BitVec = self.outputs.iter().zip(other.outputs.iter())
239            .map(|(a, b)| *a && *b)
240            .collect();
241        TruthTable {
242            num_inputs: self.num_inputs,
243            outputs,
244        }
245    }
246
247    /// Combine two truth tables using OR.
248    pub fn or_with(&self, other: &TruthTable) -> TruthTable {
249        assert_eq!(self.num_inputs, other.num_inputs);
250        let outputs: BitVec = self.outputs.iter().zip(other.outputs.iter())
251            .map(|(a, b)| *a || *b)
252            .collect();
253        TruthTable {
254            num_inputs: self.num_inputs,
255            outputs,
256        }
257    }
258
259    /// Negate the truth table.
260    pub fn negate(&self) -> TruthTable {
261        let outputs: BitVec = self.outputs.iter().map(|b| !*b).collect();
262        TruthTable {
263            num_inputs: self.num_inputs,
264            outputs,
265        }
266    }
267}
268
269#[cfg(test)]
270mod tests {
271    use super::*;
272
273    #[test]
274    fn test_and_gate() {
275        let and = TruthTable::and(2);
276        assert!(!and.evaluate(&[false, false]));
277        assert!(!and.evaluate(&[true, false]));
278        assert!(!and.evaluate(&[false, true]));
279        assert!(and.evaluate(&[true, true]));
280    }
281
282    #[test]
283    fn test_or_gate() {
284        let or = TruthTable::or(2);
285        assert!(!or.evaluate(&[false, false]));
286        assert!(or.evaluate(&[true, false]));
287        assert!(or.evaluate(&[false, true]));
288        assert!(or.evaluate(&[true, true]));
289    }
290
291    #[test]
292    fn test_not_gate() {
293        let not = TruthTable::not();
294        assert!(not.evaluate(&[false]));
295        assert!(!not.evaluate(&[true]));
296    }
297
298    #[test]
299    fn test_xor_gate() {
300        let xor = TruthTable::xor(2);
301        assert!(!xor.evaluate(&[false, false]));
302        assert!(xor.evaluate(&[true, false]));
303        assert!(xor.evaluate(&[false, true]));
304        assert!(!xor.evaluate(&[true, true]));
305    }
306
307    #[test]
308    fn test_nand_gate() {
309        let nand = TruthTable::nand(2);
310        assert!(nand.evaluate(&[false, false]));
311        assert!(nand.evaluate(&[true, false]));
312        assert!(nand.evaluate(&[false, true]));
313        assert!(!nand.evaluate(&[true, true]));
314    }
315
316    #[test]
317    fn test_implies() {
318        let imp = TruthTable::implies();
319        assert!(imp.evaluate(&[false, false])); // F -> F = T
320        assert!(imp.evaluate(&[false, true]));  // F -> T = T
321        assert!(!imp.evaluate(&[true, false])); // T -> F = F
322        assert!(imp.evaluate(&[true, true]));   // T -> T = T
323    }
324
325    #[test]
326    fn test_from_function() {
327        let majority = TruthTable::from_function(3, |input| {
328            input.iter().filter(|&&b| b).count() >= 2
329        });
330        assert!(!majority.evaluate(&[false, false, false]));
331        assert!(!majority.evaluate(&[true, false, false]));
332        assert!(majority.evaluate(&[true, true, false]));
333        assert!(majority.evaluate(&[true, true, true]));
334    }
335
336    #[test]
337    fn test_evaluate_config() {
338        let and = TruthTable::and(2);
339        assert!(!and.evaluate_config(&[0, 0]));
340        assert!(!and.evaluate_config(&[1, 0]));
341        assert!(and.evaluate_config(&[1, 1]));
342    }
343
344    #[test]
345    fn test_satisfiable() {
346        let or = TruthTable::or(2);
347        assert!(or.is_satisfiable());
348
349        let contradiction = TruthTable::from_outputs(2, vec![false, false, false, false]);
350        assert!(!contradiction.is_satisfiable());
351        assert!(contradiction.is_contradiction());
352    }
353
354    #[test]
355    fn test_tautology() {
356        let tautology = TruthTable::from_outputs(2, vec![true, true, true, true]);
357        assert!(tautology.is_tautology());
358
359        let or = TruthTable::or(2);
360        assert!(!or.is_tautology());
361    }
362
363    #[test]
364    fn test_satisfying_assignments() {
365        let xor = TruthTable::xor(2);
366        let sat = xor.satisfying_assignments();
367        assert_eq!(sat.len(), 2);
368        assert!(sat.contains(&vec![true, false]));
369        assert!(sat.contains(&vec![false, true]));
370    }
371
372    #[test]
373    fn test_count() {
374        let and = TruthTable::and(2);
375        assert_eq!(and.count_ones(), 1);
376        assert_eq!(and.count_zeros(), 3);
377    }
378
379    #[test]
380    fn test_index_to_input() {
381        let tt = TruthTable::and(3);
382        assert_eq!(tt.index_to_input(0), vec![false, false, false]);
383        assert_eq!(tt.index_to_input(1), vec![true, false, false]);
384        assert_eq!(tt.index_to_input(7), vec![true, true, true]);
385    }
386
387    #[test]
388    fn test_outputs_vec() {
389        let and = TruthTable::and(2);
390        assert_eq!(and.outputs_vec(), vec![false, false, false, true]);
391    }
392
393    #[test]
394    fn test_and_with() {
395        let a = TruthTable::from_outputs(1, vec![false, true]);
396        let b = TruthTable::from_outputs(1, vec![true, false]);
397        let result = a.and_with(&b);
398        assert_eq!(result.outputs_vec(), vec![false, false]);
399    }
400
401    #[test]
402    fn test_or_with() {
403        let a = TruthTable::from_outputs(1, vec![false, true]);
404        let b = TruthTable::from_outputs(1, vec![true, false]);
405        let result = a.or_with(&b);
406        assert_eq!(result.outputs_vec(), vec![true, true]);
407    }
408
409    #[test]
410    fn test_negate() {
411        let and = TruthTable::and(2);
412        let nand = and.negate();
413        assert_eq!(nand.outputs_vec(), vec![true, true, true, false]);
414    }
415
416    #[test]
417    fn test_num_rows() {
418        let tt = TruthTable::and(3);
419        assert_eq!(tt.num_rows(), 8);
420    }
421
422    #[test]
423    fn test_3_input_and() {
424        let and3 = TruthTable::and(3);
425        assert!(!and3.evaluate(&[true, true, false]));
426        assert!(and3.evaluate(&[true, true, true]));
427    }
428
429    #[test]
430    fn test_xnor() {
431        let xnor = TruthTable::xnor(2);
432        assert!(xnor.evaluate(&[false, false]));
433        assert!(!xnor.evaluate(&[true, false]));
434        assert!(!xnor.evaluate(&[false, true]));
435        assert!(xnor.evaluate(&[true, true]));
436    }
437
438    #[test]
439    fn test_nor() {
440        let nor = TruthTable::nor(2);
441        assert!(nor.evaluate(&[false, false]));
442        assert!(!nor.evaluate(&[true, false]));
443        assert!(!nor.evaluate(&[false, true]));
444        assert!(!nor.evaluate(&[true, true]));
445    }
446}
problemreductions/truth_table.rs

problemreductions/
truth_table.rs
