use crate::linear::fragment::Mode;
use crate::linear::occurrences::{Member, OccId, Sign};
use crate::linear::sequents::{Atom, Sequent, Symbol};
use std::fmt::{Display, Formatter, Result as FmtResult};
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Refutation {
Exhausted,
Unbalanced(Unbalanced),
OneSided(OneSided),
Equation(Equation),
StateEquation(StateEquation),
Classical(Classical),
Saturated(Saturated),
UnbalancedSymbol(UnbalancedSymbol),
OneSidedSymbol(OneSidedSymbol),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct UnbalancedSymbol {
pub symbol: Symbol,
pub least: i32,
pub most: i32,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct OneSidedSymbol {
pub symbol: Symbol,
pub least: i32,
pub most: i32,
pub copied: Sign,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct Unbalanced {
pub atom: Atom,
pub least: i32,
pub most: i32,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct OneSided {
pub atom: Atom,
pub least: i32,
pub most: i32,
pub copied: Sign,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct Equation {
pub formulas: u64,
pub needed: i64,
pub tensors: u64,
pub pars: u64,
pub ones: u64,
pub bottoms: u64,
pub mix: bool,
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct StateEquation {
pub atoms: Vec<(Atom, i64)>,
pub clauses: Vec<(OccId, i64)>,
pub dropped: Vec<OccId>,
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct Classical {
pub assignment: Vec<bool>,
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct Saturated {
pub positive: Vec<Sign>,
pub sequents: Vec<Stable>,
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct Stable {
pub linear: Vec<OccId>,
pub unrestricted: Vec<OccId>,
pub absorbs: bool,
}
impl Stable {
pub fn new(linear: Vec<OccId>, unrestricted: Vec<OccId>, absorbs: bool) -> Self {
Self {
linear,
unrestricted,
absorbs,
}
}
}
impl Saturated {
pub fn new(positive: Vec<Sign>, sequents: Vec<Stable>) -> Self {
Self { positive, sequents }
}
}
impl Refutation {
pub const NAMES: &'static [&'static str] = &[
"exhausted",
"unbalanced",
"one_sided",
"equation",
"state_equation",
"classical",
"saturated",
"unbalanced_symbol",
"one_sided_symbol",
];
pub const fn name(&self) -> &'static str {
match self {
Refutation::Exhausted => "exhausted",
Refutation::Unbalanced(_) => "unbalanced",
Refutation::OneSided(_) => "one_sided",
Refutation::Equation(_) => "equation",
Refutation::StateEquation(_) => "state_equation",
Refutation::Classical(_) => "classical",
Refutation::Saturated(_) => "saturated",
Refutation::UnbalancedSymbol(_) => "unbalanced_symbol",
Refutation::OneSidedSymbol(_) => "one_sided_symbol",
}
}
fn write(
&self,
f: &mut Formatter<'_>,
sequent: Option<&Sequent>,
intuitionistic: bool,
) -> FmtResult {
let names = sequent.map(Sequent::atom_names);
let name = |atom: Atom| match names.and_then(|names| names.get(atom.index())) {
Some(name) => name.clone(),
None => format!("#{}", atom.get()),
};
let predicate = |symbol: Symbol| match sequent.and_then(|s| s.symbols().get(symbol.index()))
{
Some((name, _)) => format!("{name}(…)"),
None => format!("#{}(…)", symbol.get()),
};
match self {
Refutation::UnbalancedSymbol(UnbalancedSymbol {
symbol,
least,
most,
}) => write_unbalanced(
f,
&predicate(*symbol),
*least,
*most,
(None, true),
intuitionistic,
),
Refutation::OneSidedSymbol(OneSidedSymbol {
symbol,
least,
most,
copied,
}) => write_unbalanced(
f,
&predicate(*symbol),
*least,
*most,
(Some(*copied), true),
intuitionistic,
),
Refutation::Exhausted => f.write_str("the search was exhaustive"),
Refutation::Unbalanced(Unbalanced { atom, least, most }) => write_unbalanced(
f,
&name(*atom),
*least,
*most,
(None, false),
intuitionistic,
),
Refutation::OneSided(OneSided {
atom,
least,
most,
copied,
}) => write_unbalanced(
f,
&name(*atom),
*least,
*most,
(Some(*copied), false),
intuitionistic,
),
Refutation::Equation(Equation {
formulas,
needed,
tensors,
pars,
ones,
bottoms,
mix,
}) => {
let needed = if *needed < 0 {
format!("−{}", needed.unsigned_abs())
} else {
needed.to_string()
};
let exactly = if *mix { "at least " } else { "exactly " };
if intuitionistic {
write!(
f,
"the count equation fails: a provable sequent of IMLL has {exactly}#⊗ᵣ + \
#⊸ₗ − #⊗ₗ − #⊸ᵣ − #1ᵣ + #1ₗ + 2 formulas (ᵣ right of ⊢, ₗ left of it, an \
implication's antecedent on the other side), here {tensors} − {pars} − \
{ones} + {bottoms} + 2 = {needed}, and this one has {formulas}",
)
} else {
write!(
f,
"the count equation fails: a provable one-sided sequent of MLL has \
{exactly}#⊗ − #⅋ − #1 + #⊥ + 2 formulas, here {tensors} − {pars} − \
{ones} + {bottoms} + 2 = {needed}, and this one has {formulas}",
)
}
}
Refutation::StateEquation(StateEquation { atoms, clauses, .. }) => {
f.write_str(
"the state equation of the Petri net has no solution, so no firing of its \
clauses yields the goal's atoms: weighting",
)?;
let once = !clauses.is_empty();
for (i, &(atom, weight)) in atoms.iter().enumerate() {
let sign = if weight < 0 { "−" } else { "" };
let between = match i {
0 => " each",
_ if i + 1 == atoms.len() && !once => " and",
_ => ",",
};
write!(
f,
"{between} {} by {sign}{}",
name(atom),
weight.unsigned_abs()
)?;
}
if once {
let between = if atoms.is_empty() { "" } else { " and" };
f.write_str(between)?;
f.write_str(" the clauses used once by weights of their own")?;
}
f.write_str(
", no clause that can fire raises the weighted count of the atoms, and the goal \
asks it raised",
)
}
Refutation::Classical(Classical { assignment }) => {
f.write_str("the classical reading is false")?;
let truths: Vec<String> = (0..assignment.len())
.filter(|&a| assignment[a])
.map(|a| name(Atom::new(a as u32)))
.collect();
match truths.len() {
_ if assignment.is_empty() => {}
0 => f.write_str(" where every atom is false")?,
n if n == assignment.len() => f.write_str(" where every atom is true")?,
n => write!(
f,
" where {} {} true and every other atom false",
list(&truths),
if n == 1 { "is" } else { "are" }
)?,
}
f.write_str(if intuitionistic {
" (! erased, ⊗ and & as and, ⊕ as or, ⊸ as implies, 1 and ⊤ true, 0 false), \
and every provable sequent reads as a tautology"
} else {
" (! and ? erased, ⊗ and & as and, ⅋ and ⊕ as or, 1 and ⊤ true, ⊥ and 0 false), \
and every provable sequent reads as a tautology"
})
}
Refutation::Saturated(Saturated { sequents, .. }) => write!(
f,
"the search saturated: {} {} closed under the rules, and the goal needs one {}",
sequents.len(),
if sequents.len() == 1 {
"sequent"
} else {
"sequents"
},
if sequents.len() == 1 {
"it does not give"
} else {
"they do not give"
},
),
}
}
}
fn list(names: &[String]) -> String {
match names {
[] => String::new(),
[one] => one.clone(),
[init @ .., last] => format!("{} and {last}", init.join(", ")),
}
}
fn write_unbalanced(
f: &mut Formatter<'_>,
name: &str,
least: i32,
most: i32,
(copied, predicate): (Option<Sign>, bool),
intuitionistic: bool,
) -> FmtResult {
let over = if predicate {
", every atom of the predicate counted, since one has a bound variable"
} else {
""
};
let (a, b) = (least.unsigned_abs(), most.unsigned_abs());
let (a, b) = (a.min(b), a.max(b));
let excess = if a == b {
format!("{a}")
} else {
format!("{a} to {b}")
};
let times = if a == 1 && b == 1 { "time" } else { "times" };
let alternatives = if a == b {
""
} else {
", whichever additive alternatives a proof takes"
};
if intuitionistic {
let (more, fewer) = if least > 0 {
("positively", "negatively")
} else {
("negatively", "positively")
};
let (place, copies) = match copied {
Some(sign) => (
" outside the exponentials",
format!(
", and every occurrence of it below one, which copies add, is {}",
match sign {
Sign::Atom => "positive",
Sign::Dual => "negative",
}
),
),
None => ("", String::new()),
};
return write!(
f,
"{name} occurs {more} {excess} more {times} than {fewer}{place}{alternatives}{copies} \
(positive right of ⊢, negative left of it, an implication's antecedent on the other \
side){over}, so they cannot all meet in axioms",
);
}
let (more, fewer) = if least > 0 {
(name.to_owned(), format!("~{name}"))
} else {
(format!("~{name}"), name.to_owned())
};
let (place, copies) = match copied {
Some(sign) => {
let literal = match sign {
Sign::Atom => name.to_owned(),
Sign::Dual => format!("~{name}"),
};
(
"outside the exponentials of the one-sided sequent",
format!(
", and every literal of the atom below one, which copies add, is {literal}"
),
)
}
None => ("in the one-sided sequent", String::new()),
};
write!(
f,
"{more} occurs {excess} more {times} than {fewer} {place}{alternatives}{copies}{over}, so \
they cannot all meet in axioms",
)
}
impl Display for Refutation {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
self.write(f, None, false)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Disproof {
sequent: Sequent,
goal: Option<Box<[Member]>>,
mode: Mode,
refutation: Refutation,
}
impl Disproof {
pub fn new(sequent: Sequent, mode: Mode, refutation: Refutation) -> Self {
Self {
sequent,
goal: None,
mode,
refutation,
}
}
#[must_use]
pub(crate) fn of_goal(self, goal: Box<[Member]>) -> Self {
Self {
goal: Some(goal),
..self
}
}
pub fn sequent(&self) -> &Sequent {
&self.sequent
}
pub fn goal(&self) -> Option<&[Member]> {
self.goal.as_deref()
}
pub fn mode(&self) -> Mode {
self.mode
}
pub fn refutation(&self) -> &Refutation {
&self.refutation
}
}
impl Display for Disproof {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
self.refutation
.write(f, Some(&self.sequent), self.mode.is_intuitionistic())
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, thiserror::Error)]
#[non_exhaustive]
pub enum RefutationFault {
#[error("a refutation of kind `{kind}` rests on the search and has no check")]
Uncertified {
kind: &'static str,
},
#[error("the {invariant} is no invariant here: {why}")]
NotApplicable {
invariant: &'static str,
why: &'static str,
},
#[error("the refutation's numbers are not those of the sequent")]
Mismatch,
#[error("the counts allow a proof")]
Holds,
#[error("the assignment gives {values} values for {atoms} atoms")]
Assignment {
atoms: usize,
values: usize,
},
#[error("the classical reading is true under the assignment")]
Satisfied,
#[error("a sequent of the saturated set is no sequent of the mode")]
Unshaped,
#[error("the saturated set is not closed under the rules")]
NotClosed,
#[error("the saturated set gives every stable sequent the goal needs")]
Filled,
}
impl RefutationFault {
pub const fn name(&self) -> &'static str {
match self {
Self::Uncertified { .. } => "uncertified",
Self::NotApplicable { .. } => "not_applicable",
Self::Mismatch => "mismatch",
Self::Holds => "holds",
Self::Assignment { .. } => "assignment",
Self::Satisfied => "satisfied",
Self::Unshaped => "unshaped",
Self::NotClosed => "not_closed",
Self::Filled => "filled",
}
}
}
impl Disproof {
pub fn check(&self) -> Result<(), crate::Error> {
let fault = |fault| crate::Error::Refutation(fault);
let forest = crate::linear::occurrences::Forest::new(&self.sequent)?;
if forest.has_binders()
&& matches!(
self.refutation,
Refutation::Classical(_) | Refutation::Saturated(_)
)
{
return Err(fault(RefutationFault::NotApplicable {
invariant: "this refutation",
why: "it is propositional, and the sequent has a quantifier",
}));
}
let goal: Vec<OccId> = match &self.goal {
None => forest.roots().to_vec(),
Some(members) => members
.iter()
.map(|m| {
m.occurrence(&forest)
.ok_or(fault(RefutationFault::Mismatch))
})
.collect::<Result<_, _>>()?,
};
match &self.refutation {
Refutation::Classical(classical) => check_classical(&forest, &goal, classical),
Refutation::Unbalanced(unbalanced) => {
check_unbalanced(&forest, &goal, self.mode, unbalanced)
}
Refutation::UnbalancedSymbol(unbalanced) => {
check_unbalanced_symbol(&forest, &goal, self.mode, unbalanced)
}
Refutation::Equation(equation) => check_equation(&forest, &goal, self.mode, equation),
Refutation::Saturated(saturated) => {
match super::saturated::check(&forest, &goal, self.mode, saturated, &mut |_| false)
{
Ok(()) => Ok(()),
Err(super::saturated::Failed::Fault(fault)) => Err(fault),
Err(super::saturated::Failed::Stopped) => {
unreachable!("a check without a stop runs to its end")
}
}
}
Refutation::OneSided(one_sided) => {
check_one_sided(&forest, &goal, self.mode, one_sided)
}
Refutation::OneSidedSymbol(one_sided) => {
check_one_sided_symbol(&forest, &goal, self.mode, one_sided)
}
Refutation::StateEquation(equation) => {
super::weighted::state_equation(&forest, &goal, self.mode, equation).map(|_| ())
}
refutation @ Refutation::Exhausted => Err(RefutationFault::Uncertified {
kind: refutation.name(),
}),
}
.map_err(fault)
}
}
fn check_classical(
forest: &crate::linear::occurrences::Forest,
goal: &[OccId],
classical: &Classical,
) -> Result<(), RefutationFault> {
use crate::linear::sequents::Kind::*;
let (atoms, values) = (
forest.sequent().atom_names().len(),
classical.assignment.len(),
);
if atoms != values {
return Err(RefutationFault::Assignment { atoms, values });
}
let value = |o: OccId| {
let atom = forest.atom(o).map(|a| classical.assignment[a.index()]);
atom.unwrap_or(false)
};
let mut truth = vec![false; forest.len()];
for &member in goal {
for o in forest.subtree(member).rev() {
let side = |side: Option<OccId>| side.is_some_and(|s| truth[s.index()]);
let (l, r) = (side(forest.left(o)), side(forest.right(o)));
truth[o.index()] = match forest.kind(o) {
Atom => value(o),
DualAtom => !value(o),
One | Top => true,
Bot | Zero => false,
Tensor | With => l && r,
Par | Plus => l || r,
Bang | Quest => l,
Forall | Exists => {
unreachable!("an assignment of a sequent with a binder is refused")
}
};
}
if truth[member.index()] {
return Err(RefutationFault::Satisfied);
}
}
Ok(())
}
fn check_unbalanced(
forest: &crate::linear::occurrences::Forest,
goal: &[OccId],
mode: Mode,
unbalanced: &Unbalanced,
) -> Result<(), RefutationFault> {
let atom = unbalanced.atom;
let sequent = forest.sequent();
if atom.index() >= sequent.atom_names().len() {
return Err(RefutationFault::Mismatch);
}
if let Some((symbol, _)) = sequent.atom_predicate(atom)
&& (0..sequent.atom_names().len()).any(|a| {
let a = Atom::new(a as u32);
sequent.atom_predicate(a).map(|(s, _)| s) == Some(symbol) && sequent.atom_is_open(a)
})
{
return Err(RefutationFault::NotApplicable {
invariant: "balance of the atom",
why: "an atom of its predicate has a bound variable, whose instance may be it",
});
}
check_balance(
forest,
goal,
mode,
|o| forest.atom(o) == Some(atom),
(unbalanced.least, unbalanced.most),
)
}
fn check_unbalanced_symbol(
forest: &crate::linear::occurrences::Forest,
goal: &[OccId],
mode: Mode,
unbalanced: &UnbalancedSymbol,
) -> Result<(), RefutationFault> {
let sequent = forest.sequent();
if unbalanced.symbol.index() >= sequent.symbols().len() {
return Err(RefutationFault::Mismatch);
}
check_balance(
forest,
goal,
mode,
|o| {
forest
.atom(o)
.and_then(|a| sequent.atom_predicate(a))
.is_some_and(|(s, _)| s == unbalanced.symbol)
},
(unbalanced.least, unbalanced.most),
)
}
fn check_balance(
forest: &crate::linear::occurrences::Forest,
goal: &[OccId],
mode: Mode,
counted: impl Fn(OccId) -> bool,
stated: (i32, i32),
) -> Result<(), RefutationFault> {
use crate::linear::sequents::Kind::*;
const INVARIANT: &str = "balance of the atom";
if mode.affine {
return Err(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "weakening discards literals",
});
}
let mut span: Vec<Option<(i64, i64)>> = vec![None; forest.len()];
let (mut least, mut most) = (0, 0);
for &member in goal {
for o in forest.subtree(member).rev() {
let side = |side: Option<OccId>| side.and_then(|s| span[s.index()]);
let (l, r) = (side(forest.left(o)), side(forest.right(o)));
let literal = |e| Some(if counted(o) { (e, e) } else { (0, 0) });
span[o.index()] = match forest.kind(o) {
Atom => literal(1),
DualAtom => literal(-1),
One | Bot | Zero => Some((0, 0)),
Top => None,
Tensor | Par => l.zip(r).map(|((a, b), (c, d))| (a + c, b + d)),
With | Plus => l.zip(r).map(|((a, b), (c, d))| (a.min(c), b.max(d))),
Bang | Quest => l.filter(|&s| s == (0, 0)),
Forall | Exists => l,
};
}
let Some((lo, hi)) = span[member.index()] else {
return Err(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "a ⊤ absorbs, or copies of the atom's literals add any number",
});
};
(least, most) = (least + lo, most + hi);
}
if (least, most) != (i64::from(stated.0), i64::from(stated.1)) {
Err(RefutationFault::Mismatch)
} else if least <= 0 && 0 <= most {
Err(RefutationFault::Holds)
} else {
Ok(())
}
}
fn check_one_sided(
forest: &crate::linear::occurrences::Forest,
goal: &[OccId],
mode: Mode,
one_sided: &OneSided,
) -> Result<(), RefutationFault> {
let atom = one_sided.atom;
let sequent = forest.sequent();
if atom.index() >= sequent.atom_names().len() {
return Err(RefutationFault::Mismatch);
}
if let Some((symbol, _)) = sequent.atom_predicate(atom)
&& (0..sequent.atom_names().len()).any(|a| {
let a = Atom::new(a as u32);
sequent.atom_predicate(a).map(|(s, _)| s) == Some(symbol) && sequent.atom_is_open(a)
})
{
return Err(RefutationFault::NotApplicable {
invariant: "one-sided count of the atom",
why: "an atom of its predicate has a bound variable, whose instance may be it",
});
}
check_copies(
forest,
goal,
mode,
|o| forest.atom(o) == Some(atom),
(one_sided.least, one_sided.most, one_sided.copied),
)
}
fn check_one_sided_symbol(
forest: &crate::linear::occurrences::Forest,
goal: &[OccId],
mode: Mode,
one_sided: &OneSidedSymbol,
) -> Result<(), RefutationFault> {
let sequent = forest.sequent();
if one_sided.symbol.index() >= sequent.symbols().len() {
return Err(RefutationFault::Mismatch);
}
check_copies(
forest,
goal,
mode,
|o| {
forest
.atom(o)
.and_then(|a| sequent.atom_predicate(a))
.is_some_and(|(s, _)| s == one_sided.symbol)
},
(one_sided.least, one_sided.most, one_sided.copied),
)
}
fn check_copies(
forest: &crate::linear::occurrences::Forest,
goal: &[OccId],
mode: Mode,
counted: impl Fn(OccId) -> bool,
(least, most, copied): (i32, i32, Sign),
) -> Result<(), RefutationFault> {
use crate::linear::sequents::Kind::*;
const INVARIANT: &str = "one-sided count of the atom";
if mode.affine {
return Err(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "weakening discards literals",
});
}
let mut span: Vec<Option<(i64, i64)>> = vec![None; forest.len()];
let mut below = [false; 2];
let (mut lo, mut hi) = (0i64, 0i64);
for &member in goal {
let mut inside = 0;
for o in forest.subtree(member) {
if o.index() < inside
&& let Some(sign) = forest.sign(o)
&& counted(o)
{
below[sign as usize] = true;
}
if matches!(forest.kind(o), Bang | Quest) {
inside = inside.max(o.index() + forest.size(o) as usize);
}
}
for o in forest.subtree(member).rev() {
let side = |side: Option<OccId>| side.and_then(|s| span[s.index()]);
let (l, r) = (side(forest.left(o)), side(forest.right(o)));
let literal = |e| Some(if counted(o) { (e, e) } else { (0, 0) });
span[o.index()] = match forest.kind(o) {
Atom => literal(1),
DualAtom => literal(-1),
One | Bot | Zero => Some((0, 0)),
Top => None,
Tensor | Par => l.zip(r).map(|((a, b), (c, d))| (a + c, b + d)),
With | Plus => l.zip(r).map(|((a, b), (c, d))| (a.min(c), b.max(d))),
Bang | Quest => l.map(|_| (0, 0)),
Forall | Exists => l,
};
}
let Some((a, b)) = span[member.index()] else {
return Err(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "a ⊤ absorbs",
});
};
let (Some(a), Some(b)) = (lo.checked_add(a), hi.checked_add(b)) else {
return Err(RefutationFault::Mismatch);
};
(lo, hi) = (a, b);
}
match below {
[true, true] => {
return Err(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "copies add literals of both signs",
});
}
[positive, negative]
if positive && copied == Sign::Dual || negative && copied == Sign::Atom =>
{
return Err(RefutationFault::Mismatch);
}
_ => {}
}
if (lo, hi) != (i64::from(least), i64::from(most)) {
return Err(RefutationFault::Mismatch);
}
let excluded = match copied {
Sign::Atom => lo > 0,
Sign::Dual => hi < 0,
};
if !excluded {
return Err(RefutationFault::Holds);
}
let weight = match copied {
Sign::Atom => 1,
Sign::Dual => -1,
};
let weights = super::weighted::Weights {
weight: &|o| if counted(o) { weight } else { 0 },
dead: &|_| false,
sign: Sign::Atom,
weakening: false,
};
super::weighted::overweight(forest, goal, &weights)
}
fn check_equation(
forest: &crate::linear::occurrences::Forest,
goal: &[OccId],
mode: Mode,
equation: &Equation,
) -> Result<(), RefutationFault> {
use crate::linear::sequents::Kind::*;
const INVARIANT: &str = "count equation";
if mode.affine {
return Err(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "weakening adds formulas",
});
}
let (mut tensors, mut pars, mut ones, mut bottoms) = (0u64, 0u64, 0u64, 0u64);
for &member in goal {
for o in forest.subtree(member) {
match forest.kind(o) {
Tensor => tensors += 1,
Par => pars += 1,
One => ones += 1,
Bot => bottoms += 1,
Atom | DualAtom | Forall | Exists => {}
Top | Zero | With | Plus | Bang | Quest => {
return Err(RefutationFault::NotApplicable {
invariant: INVARIANT,
why: "it holds in the multiplicative fragment with units alone",
});
}
}
}
}
let needed = tensors as i64 - pars as i64 - ones as i64 + bottoms as i64 + 2;
let formulas = goal.len() as u64;
let stated = Equation {
formulas,
needed,
tensors,
pars,
ones,
bottoms,
mix: mode.mix,
};
if *equation != stated {
return Err(RefutationFault::Mismatch);
}
let holds = if mode.mix {
formulas as i64 >= needed
} else {
formulas as i64 == needed
};
if holds {
Err(RefutationFault::Holds)
} else {
Ok(())
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::search::{Options, Verdict, prove};
fn refuted(input: &str, mode: Mode) -> Disproof {
let sequent: Sequent = input.parse().unwrap();
match prove(&sequent, mode, &Options::default()).unwrap().verdict {
Verdict::Unprovable(disproof) => *disproof,
other => panic!("{input}: {other:?}"),
}
}
fn claimed(input: &str, mode: Mode, refutation: Refutation) -> Disproof {
Disproof::new(input.parse().unwrap(), mode, refutation)
}
fn fault(disproof: &Disproof) -> Option<RefutationFault> {
match disproof.check() {
Ok(()) => None,
Err(crate::Error::Refutation(fault)) => Some(fault),
Err(other) => panic!("{other:?}"),
}
}
#[test]
fn a_wrong_refutation_is_rejected() {
let classical = Mode::CLASSICAL;
let assignment = |values: &[bool]| {
Refutation::Classical(Classical {
assignment: values.to_vec(),
})
};
let found = refuted("|- a & b, ~a", classical);
assert_eq!(fault(&found), None);
assert_eq!(fault(&refuted("a, a -o b |- b * a", classical)), None);
let wrong = claimed("|- a & b, ~a", classical, assignment(&[true, true]));
assert_eq!(fault(&wrong), Some(RefutationFault::Satisfied));
let short = claimed("|- a & b, ~a", classical, assignment(&[true]));
assert_eq!(
fault(&short),
Some(RefutationFault::Assignment {
atoms: 2,
values: 1
})
);
let ill = refuted("a + b |- a", Mode::INTUITIONISTIC);
assert!(matches!(ill.refutation(), Refutation::Classical(_)));
assert_eq!(fault(&ill), None);
let unbalanced = |atom: u32, least: i32, most: i32| {
Refutation::Unbalanced(Unbalanced {
atom: Atom::new(atom),
least,
most,
})
};
let found = refuted("|- (a * a) + (a * a * a), ~a", classical);
assert_eq!(found.refutation(), &unbalanced(0, 1, 2));
assert_eq!(fault(&found), None);
let mix = refuted("a |- b", classical.with_mix());
assert!(matches!(mix.refutation(), Refutation::Unbalanced(_)));
assert_eq!(fault(&mix), None);
for (input, mode, refutation, expected) in [
(
"|- a, ~a",
classical,
unbalanced(0, 0, 0),
RefutationFault::Holds,
),
(
"|- a, ~a",
classical,
unbalanced(0, 1, 1),
RefutationFault::Mismatch,
),
(
"|- a, a",
classical,
unbalanced(1, 2, 2),
RefutationFault::Mismatch,
),
(
"|- a + ~a, a",
classical,
unbalanced(0, 1, 1),
RefutationFault::Mismatch,
),
(
"|- a + ~a, a",
classical,
unbalanced(0, 0, 2),
RefutationFault::Holds,
),
] {
assert_eq!(
fault(&claimed(input, mode, refutation)),
Some(expected),
"{input}"
);
}
for (input, mode) in [
("|- a, a", classical.with_affine()),
("|- a, a, top", classical),
("|- ?a, a", classical),
] {
assert!(
matches!(
fault(&claimed(input, mode, unbalanced(0, 2, 2))),
Some(RefutationFault::NotApplicable { .. })
),
"{input}"
);
}
let found = refuted("|- a par b, ~a, ~b", classical);
let Refutation::Equation(equation) = *found.refutation() else {
panic!("{found:?}");
};
assert_eq!(fault(&found), None);
let stated = |input: &str, mode: Mode, equation: Equation| {
fault(&claimed(input, mode, Refutation::Equation(equation)))
};
let with_mix = Equation {
mix: true,
..equation
};
assert_eq!(
stated("|- a par b, ~a, ~b", classical, with_mix),
Some(RefutationFault::Mismatch)
);
assert_eq!(
stated("|- a par b, ~a, ~b", classical.with_mix(), with_mix),
Some(RefutationFault::Holds)
);
let holds = Equation {
formulas: 2,
needed: 2,
tensors: 0,
pars: 0,
ones: 0,
bottoms: 0,
mix: false,
};
assert_eq!(
stated("|- a, ~a", classical, holds),
Some(RefutationFault::Holds)
);
for (input, mode) in [
("|- a par b, ~a, ~b", classical.with_affine()),
("|- a & b, ~a, ~b", classical),
("|- ?(a par b), ~a, ~b", classical),
] {
assert!(
matches!(
stated(input, mode, equation),
Some(RefutationFault::NotApplicable { .. })
),
"{input}"
);
}
let exhausted = claimed("|- a & b, ~a", classical, Refutation::Exhausted);
let error = exhausted.check().unwrap_err();
assert_eq!(
(error.code(), error.kind()),
("uncertified", crate::ErrorKind::Unsupported)
);
let error = wrong.check().unwrap_err();
assert_eq!(
(error.code(), error.kind()),
("invalid_refutation", crate::ErrorKind::Invalid)
);
}
#[test]
fn a_wrong_count_with_copies_or_state_equation_is_refused() {
let (classical, ill) = (Mode::CLASSICAL, Mode::INTUITIONISTIC);
for (input, mode, kind) in [
("!d, !((c * d * d) -o 1) |- c * c", classical, "one_sided"),
("!d, !((c * d * d) -o 1) |- c * c", ill, "one_sided"),
("|- ~a * ~a, ?(~a * b), ~b", classical, "one_sided"),
(
"!(a -o a * a), !(a * c -o b * c), a |- b",
ill,
"state_equation",
),
(
"!(a -o a * a), !(a * c -o b * c), a |- b",
classical.with_mix(),
"state_equation",
),
(
"|- a, ?(~a * (a par a)), ?((~a * ~c) * b), ~b",
classical,
"state_equation",
),
(
"a, a -o b, !(b -o b * c), !(b -o d) |- b * d",
ill,
"state_equation",
),
(
"!(a -o a * c), !(a -o b), a |- a * b",
ill.with_affine(),
"state_equation",
),
(
"|- a, ?(~a * (a par c)), ?(~a * b), ~a * ~b",
classical.with_affine(),
"state_equation",
),
] {
let found = refuted(input, mode);
assert_eq!(found.refutation().name(), kind, "{input}");
assert_eq!(fault(&found), None, "{input}");
}
let one_sided = |atom: u32, least: i32, most: i32, copied: Sign| {
Refutation::OneSided(OneSided {
atom: Atom::new(atom),
least,
most,
copied,
})
};
let counted = "!d, !((c * d * d) -o 1) |- c * c";
for (input, mode, refutation, expected) in [
(
counted,
classical,
one_sided(1, 1, 1, Sign::Atom),
RefutationFault::Mismatch,
),
(
counted,
classical,
one_sided(1, 2, 2, Sign::Dual),
RefutationFault::Mismatch,
),
(
"|- c * c, ?~c",
classical,
one_sided(0, 2, 2, Sign::Dual),
RefutationFault::Holds,
),
(
"|- ~c, ~c, ?c",
classical,
one_sided(0, -2, -2, Sign::Dual),
RefutationFault::Mismatch,
),
(
"|- ~c, ~c, ?c",
classical,
one_sided(0, -2, -2, Sign::Atom),
RefutationFault::Holds,
),
] {
let planted = claimed(input, mode, refutation);
assert_eq!(fault(&planted), Some(expected), "{input}");
}
for (input, mode, atom) in [
(counted, classical.with_affine(), 1),
("|- c * c, ?~c, ?c", classical, 0),
("|- c * c, ?~c, top", classical, 0),
] {
assert!(
matches!(
fault(&claimed(input, mode, one_sided(atom, 2, 2, Sign::Atom))),
Some(RefutationFault::NotApplicable { .. })
),
"{input}"
);
}
let weighed = |atoms: &[(u32, i64)]| {
Refutation::StateEquation(StateEquation {
atoms: atoms.iter().map(|&(a, w)| (Atom::new(a), w)).collect(),
clauses: Vec::new(),
dropped: Vec::new(),
})
};
let net = "!(a -o a * a), !(a * c -o b * c), a |- b";
let found = refuted(net, ill);
let Refutation::StateEquation(equation) = found.refutation() else {
panic!("{found:?}");
};
assert_eq!(equation.atoms, [(Atom::new(0), -1), (Atom::new(2), 1)]);
for (input, mode, atoms, expected) in [
(
"a, a -o b, !(b -o b * c), !(b -o d) |- b * d",
ill,
&[(0, 1), (1, 1), (3, 2)][..],
RefutationFault::Holds,
),
(
"a, a -o b, !(b -o b * c), !(b -o d) |- b * d",
ill,
&[(0, 2), (1, 1), (2, 1), (3, 1)][..],
RefutationFault::Holds,
),
(net, ill, &[(2, 1), (0, -1)][..], RefutationFault::Mismatch),
(net, ill, &[(0, -1), (7, 1)][..], RefutationFault::Mismatch),
(
"|- a, ?(~a * (a par c)), ?(~a * b), ~a * ~b",
classical.with_affine(),
&[(0, 1), (1, 1), (2, 1)][..],
RefutationFault::Holds,
),
] {
let planted = claimed(input, mode, weighed(atoms));
assert_eq!(fault(&planted), Some(expected), "{input}");
}
for (input, mode) in [
("|- a & b, ~a", classical),
("|- ~a, ~a", classical.with_affine()),
("forall x. p(x) |- p(c)", classical),
] {
assert!(
matches!(
fault(&claimed(input, mode, weighed(&[(0, 1)]))),
Some(RefutationFault::NotApplicable { .. })
),
"{input}"
);
}
}
}