Tag: perfect circle
Logic on Math StackExchange
- Can This Rieger-Nishimura-Based Decision Procedure for Intuitionistic Propositional Logic Be Optimized Past This Brute-Force Approach? March 22, 2025I took a fair amount of time after some previous posts (here and here) to look over potential compositional decision procedures for IPL, and decided (against sound advice from Kocsis which discouraged this approach) to take another bite at this apple. I did come up with such a procedure that does not rely on a […]Joshua Harwood
- law of the excluded middle March 21, 2025Consider a language $\mathcal{L}$ with a single unary predicate $P$. In intuitionstic logic, is it true that if $(\forall x)(P(x) \vee \neg P(x))$, then the law of the excluded middle holds for any formula of $\mathcal{L}$? That is to say, for any closed formula $X$ of $\mathcal{L}$, is $$(\forall x)(P(x) \vee \neg P(x)) \rightarrow (X […]provocateur
- Why Induction on Both the Number of Variables and the Number of Wide Clauses in the Proof of Resolution Width? March 20, 2025I am trying to understand the proof of the inequality $$ w(F) \leq iw(F) + 1 + 3\sqrt{\ln S(F)} $$ where: $w(F)$ is the minimal width of a resolution refutation of $F$, $iw(F)$ is the initial width (the width of the largest clause in $F$), $S(F)$ is the size of a minimum refutation of $F$ […]Tony Starck
- Particular name for the second propositional variable in the hypothetical syllogism? March 20, 2025The hypothetical syllogism states that: $$ \begin{array}{ l } p \rightarrow q \\ q \rightarrow r \\ \hline p \rightarrow r \end{array} $$ Is there a particular name used for the premise $q$ here? The context is that I'm considering the task of finding a $q$ such that $p \rightarrow q$ and $q \rightarrow r$ […]Rasmus Källqvist
- Prove that formulas in $\{\land,\lor,0,1\}$ represents exactly the monotonic boolean functions March 18, 2025The Problem from Rautenberg's A Concise Introduction to Mathematical Logic: Show that the formulas in $\land,\lor,0,1$ represents exactly the monotonic Boolean functions. These are the constants from boolean function of order $0$, $B_0$, and for $n>0$ the $f\in B_n$ such that for all $i$ with $1\le i\le n$, $$f(x_1,\cdots,x_{i-1},0,\cdots,x_n)\leq f(x_1,\cdots,x_{i-1},1,x_{i+1},\cdots,x_n)$$ The hint given is here: […]Liyang Meng
- Logic: is LHS of equality distributive across RHS OR? [duplicate] March 18, 2025Is LHS of equality distributive across RHS OR? For example, is the following a valid change of form to solve for $y$? $T = T \land y$ Negate both sides, DeMorgans Law: $F = F \lor \lnot y$ Distribute across equality? $\lnot y = F, F = F$ Negate both sides: $y = T, T […]atod
- Generalization in propositional calculus (Mendelson's book on Mathematical Logic) March 17, 2025In Section 2.4 of Mendelson's Introduction to Mathematical Logic (6th Edition), below the proof of Corollary 2.3, the author cautions against an unqualified application of the deduction theorem à la propositional calculus in the predicate one. To clarify this distinction, a small counterexample is presented — one that I can't fully understand... Counterexample: "...for any […]WhatAbouty
- Prove that each formula $\alpha$ in signature $\{\neg, +\}$ represents a linear Boolean function March 17, 2025$f\in\boldsymbol{B}_n$ is called linear if $f(x_1,\ldots,x_n)=a_0+a_1x_1+\cdots+a_nx_n$ for suitable coefficients $a_0, \ldots , a_n\in \{ 0, 1\}.$ Here + denotes exclusive disjunction (addition modulo 2) and the not written multiplication is conjunction (i.e., $a_ix_i=x_i$ for $a_i=1$ and $a_ix_i=0$ for $a_i=0).$ (a) Show that the above representation of a linear function $f$ is unique. (b) Determine the […]Liyang Meng
- Does ZF-FA $\vdash$ $\exists x (x = \{x\})?$ March 17, 2025A set is called reflexive iff x = {x}. An atom or unrelement is not a set but it can be an element of a set. Given ZF.We get ZFA if we allow atom and don't allow reflexive sets. If we want get reflexive sets, we must remove FA. It seems that $\vdash Con ($ZF-FA […]whiston
- Laver's theorem, reference March 16, 2025Is there a recent paper or book's chapter that proves Laver's theorem on Fraïssé's conjecture, apart from Laver's original paper On Fraissé’s order type conjecture? ThanksLorenzo
Recent Comments