use super::{Logic, Node, NodeId, Sequent};
use crate::Error;
use crate::kripke::{Model, World};
use crate::limits::{Limits, Phase, Progress, Refusal};
use std::fmt::{self, Display, Formatter, Write};
#[derive(Clone, Debug)]
pub struct TruthTable {
sequent: Sequent,
bits: Vec<u64>,
falsifying: Vec<u64>,
}
impl TruthTable {
pub fn sequent(&self) -> &Sequent {
&self.sequent
}
pub fn atoms(&self) -> usize {
self.sequent.formulas().atom_names().len()
}
pub fn rows(&self) -> u64 {
1 << self.atoms()
}
pub fn assigns(&self, row: u64, atom: usize) -> bool {
let atoms = self.atoms();
assert!(
row < self.rows() && atom < atoms,
"a row and an atom of the table"
);
row >> (atoms - 1 - atom) & 1 == 0
}
pub fn value(&self, row: u64, id: NodeId) -> bool {
let width = self.sequent.formulas().len();
assert!(
row < self.rows() && id.index() < width,
"a row and a formula of the table"
);
let cell = row as usize * width + id.index();
self.bits[cell / 64] >> (cell % 64) & 1 == 1
}
pub fn row(&self, row: u64) -> impl Iterator<Item = bool> + '_ {
let width = self.sequent.formulas().len();
(0..width).map(move |id| self.value(row, NodeId(id as u32)))
}
pub fn falsifies(&self, row: u64) -> bool {
self.falsifying.binary_search(&row).is_ok()
}
pub fn falsifying(&self) -> &[u64] {
&self.falsifying
}
pub fn model(&self, row: u64) -> Model {
let names = self.sequent.formulas().atom_names();
let atoms = (0..names.len())
.filter(|&a| self.assigns(row, a))
.map(|a| names[a].clone())
.collect();
Model::new(vec![World::new(atoms, false, Vec::new())], 0)
}
}
impl TruthTable {
pub fn write_text(&self, out: &mut impl Write) -> fmt::Result {
let formulas = self.sequent.formulas();
let names = formulas.atom_names();
let mut columns: Vec<(String, Option<NodeId>)> =
names.iter().map(|name| (name.clone(), None)).collect();
let atoms = columns.len();
for &id in self.sequent.left().iter().chain(self.sequent.right()) {
columns.push((formulas.formula(id).to_string(), Some(id)));
}
let widths: Vec<usize> = columns.iter().map(|(h, _)| h.chars().count()).collect();
let hypotheses = atoms + self.sequent.left().len();
let gap = |c: usize| match c {
0 => "",
c if c == atoms => " │ ",
c if c == hypotheses => " ⊢ ",
_ => " ",
};
let gap = |c: usize| {
if c == hypotheses && c == atoms {
" │ ⊢ "
} else {
gap(c)
}
};
for (c, (header, _)) in columns.iter().enumerate() {
write!(out, "{}{header}", gap(c))?;
}
if atoms == columns.len() || hypotheses == columns.len() {
write!(out, "{}", gap(columns.len()))?;
}
let under = |c: usize| if c == atoms { gap(c) } else { " " };
let mut line = String::new();
for row in 0..self.rows() {
line.clear();
for (c, (_, id)) in columns.iter().enumerate() {
let value = match id {
None => self.assigns(row, c),
Some(id) => self.value(row, *id),
};
let letter = if value { 'T' } else { 'F' };
let before = (widths[c] - 1) / 2;
let after = widths[c] - 1 - before;
let gap = if c == hypotheses && c != atoms {
under(c)
} else {
gap(c)
};
write!(line, "{gap}{:before$}{letter}{:after$}", "", "")?;
}
if self.falsifies(row) {
line.push_str(" ×");
}
write!(out, "\n{}", line.trim_end())?;
}
Ok(())
}
}
impl Display for TruthTable {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
self.write_text(f)
}
}
pub fn truth_table(
sequent: &Sequent,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<TruthTable, Error> {
let formulas = sequent.formulas();
let atoms = formulas.atom_names().len() as u64;
let width = formulas.len() as u64;
if let Some(limit) = limits.table_atoms
&& atoms > u64::from(limit)
{
return Err(Error::Refused(Refusal::Atoms {
atoms,
limit: u64::from(limit),
}));
}
let rows = 1u64.checked_shl(atoms as u32).filter(|_| atoms < 64);
let cells = rows.and_then(|rows| rows.checked_mul(width));
let needed = cells.zip(rows).map_or(u64::MAX, |(cells, rows)| {
cells.div_ceil(8).saturating_add(rows.saturating_mul(8))
});
if let Some(limit) = limits.memory_bytes
&& needed > limit
{
return Err(Error::Refused(Refusal::Memory {
phase: Phase::Search,
limit_bytes: limit,
needed_bytes: Some(needed),
}));
}
let (Some(rows), Some(cells)) = (rows, cells) else {
return Err(index(atoms));
};
if let Some(limit) = limits.work
&& rows > limit
{
return Err(Error::Refused(Refusal::Work { limit }));
}
let Ok(cells) = usize::try_from(cells) else {
return Err(index(atoms));
};
let width = width as usize;
let mut bits = vec![0u64; cells.div_ceil(64)];
let mut falsifying = Vec::new();
let mut values = vec![false; width];
for row in 0..rows {
if stop(Progress::new(Phase::Search, 1, row + 1)) {
return Err(Error::Refused(Refusal::Stopped {
phase: Phase::Search,
}));
}
for id in 0..width {
let at = |k: NodeId| values[k.index()];
values[id] = match formulas.node(NodeId(id as u32)) {
Node::Atom(a) => row >> (atoms - 1 - u64::from(a)) & 1 == 0,
Node::True => true,
Node::False => false,
Node::Not(a) => !at(a),
Node::And(a, b) => at(a) && at(b),
Node::Or(a, b) => at(a) || at(b),
Node::Implies(a, b) => !at(a) || at(b),
Node::Iff(a, b) => at(a) == at(b),
};
}
let start = row as usize * width;
for (id, &value) in values.iter().enumerate() {
let cell = start + id;
bits[cell / 64] |= u64::from(value) << (cell % 64);
}
if sequent.left().iter().all(|h| values[h.index()])
&& sequent.right().iter().all(|c| !values[c.index()])
{
falsifying.push(row);
}
}
Ok(TruthTable {
sequent: sequent.clone(),
bits,
falsifying,
})
}
fn index(atoms: u64) -> Error {
Error::Refused(Refusal::Index {
what: crate::limits::Space::Atom,
count: atoms,
most: 63,
})
}
pub(super) fn decide(
sequent: &Sequent,
logic: Logic,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<super::Outcome, Error> {
if logic != Logic::Classical {
return Err(Error::Logic {
logic,
method: super::Method::Table,
});
}
let table = truth_table(sequent, limits, &mut stop)?;
let (verdict, countermodel) = match table.falsifying().first() {
None => (super::Verdict::Valid(super::Evidence::Table), None),
Some(&row) => {
let model = table.model(row);
let countermodel =
super::Countermodel::found(sequent.clone(), model, logic, limits, &mut stop)?;
(super::Verdict::NotValid, countermodel)
}
};
Ok(super::Outcome {
verdict,
logic,
search: super::Search::Table(Box::new(table)),
countermodel,
})
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::{Logic, Sequent, truth_table};
use crate::{Error, Limits, Refusal};
#[test]
fn a_table_marks_the_rows_that_falsify_the_sequent() {
let limits = Limits::default();
let sequent: Sequent = "a -> b |- b -> a".parse().unwrap();
let table = truth_table(&sequent, &limits, |_| false).unwrap();
assert_eq!(table.rows(), 4);
assert!(table.assigns(0, 0) && table.assigns(0, 1));
assert!(table.assigns(1, 0) && !table.assigns(1, 1));
assert_eq!(table.falsifying(), [2]);
assert!(table.falsifies(2) && !table.falsifies(1));
assert_eq!(
table
.model(2)
.refutes(&sequent, Logic::Classical, &limits, |_| false),
Ok(())
);
let valid: Sequent = "|- a \\/ ~a".parse().unwrap();
assert_eq!(
table.to_string(),
"a b │ a → b ⊢ b → a\n\
T T │ T T\n\
T F │ F T\n\
F T │ T F ×\n\
F F │ T T"
);
let valid = truth_table(&valid, &limits, |_| false).unwrap();
assert_eq!(valid.falsifying(), [0u64; 0]);
let three: Sequent = "a, b |- c".parse().unwrap();
assert_eq!(
truth_table(&three, &limits.with_table_atoms(Some(2)), |_| false).err(),
Some(Error::Refused(Refusal::Atoms { atoms: 3, limit: 2 }))
);
}
}