Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [propositional-calculus]

Appropriate for questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions. Also for general questions about the propositional calculus itself, including its semantics and proof theory. Questions about other kinds of logic should use a different tag, such as (logic), (predicate-logic), or (first-order-logic).

6
votes
0answers
191 views

What is this property exhibited by some logical systems?

The following property exhibited by some logical systems has captured my attention: $$\forall X\; ( {\vdash x_1[X]} \implies {\vdash x_2[X]} ) \implies \forall X\; {\vdash (x_1[X]\to x_2[X])},$$ ...
5
votes
0answers
95 views

How do I translate $ [(P \Rightarrow Q) \land (Q \Rightarrow T)] \Rightarrow T$ into English?

In his book, Axioms & Set Theory, Robert Andre introduces logic with this statement: If $Q$ is true whenever $P$ is true, and $T$ is true whenever $Q$ is true, then $T$ is true whenever $P$ is ...
4
votes
0answers
66 views

Is the consequence relation of a finite set of boolean connectives finitely generated?

Let $S$ be the set of all n-ary functions on $\{0,1\}$ for all n, including the 0-ary functions. Let $F$ be a finite subset of $S$. Consider a countably infinite set of propositional constants $PROP$. ...
4
votes
0answers
427 views

Is the rule of explosion (aka ex falso sequitur quodlibet) something that needs to be proved?

On this and this pages, there are proofs presented for this rule, but what confuses me though is that I think we actually need to show that $\bot\vdash Q$ holds, not $(P\wedge\neg P)\vdash Q$ or $\...
3
votes
0answers
37 views

Proof of Completeness Theorem in Enderton's Logic, satisfiability of $\Gamma \cup \Theta \cup \Lambda$

I'm reading the proof of the Completeness Theorem from Enderton's "A Mathematical Introduction to Logic". I'm having issues seeing how the following highlighted sentence actually holds (excerpt from ...
3
votes
0answers
55 views

What will be the notion of a “valid deduction” in the following system?

Consider the Propositional Calculus whose axiom schemes and rule of inference are given below (here $P,Q$ and $S$ are formula schemes, $\color{crimson}{\text{Axiom 1.}}\ P\to (Q\to P)$ $\...
3
votes
0answers
219 views

Does every CNF formula have an equivalent 2-CNF formula?

From Wolfram MathWorld: A statement is in conjunctive normal form if it is a conjunction (sequence of ANDs) consisting of one or more conjuncts, each of which is a disjunction (OR) of one or more ...
3
votes
0answers
549 views

How many ternary functionally complete connectives are there?

Today I was reading up once more on some of the nice results regarding functional completeness, notably Post's celebrated classification theorem with the 5 classes that need to be avoided. (See this ...
3
votes
0answers
115 views

Trouble at translating natural language to propositional logic and proving conclusion from it.

Given this set of premises: Something in the forest I hadn't observed was not the dark ruler Something which had been noted means worth to be remembered Something I had seen in the forest not ...
3
votes
0answers
91 views

Is the following derivation of Gödel's Paradox generalizable to an intuitionistic one using provability?

I will follow Goedel's original proof of Goedel's paradox located on pg. 264 of Hao Wang's A Logical Journey: From Gödel to Philosophy. With this in sight, and to also avoid confusion, I will also ...
3
votes
0answers
143 views

Application of the compactness theorem

In my logic book they ask me to prove the following as a consequence of the compactness theorem for propositional logic. Let $S \subseteq N$ be an infinite set. I have to show that there exists an ...
3
votes
0answers
613 views

meaning of ``partial converse''

In the definition of a commutative ring $(R,+,\times)$, one of the postulates given is that of uniqueness, i.e. that $$ a=a', b=b'\implies a+b=a'+b', ab=a' b'.$$ The text states that for the system $\...
3
votes
0answers
144 views

Boolean combinatorics

Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i \...
2
votes
0answers
44 views

Arguments by case

I am taking real analysis, but that is really not important.....the important part is that my professor says that one of my methods of proof is invalid. Essentially he is asking me to prove something ...
2
votes
0answers
98 views

How many distinct subsets of binary boolean operators are closed under composition?

Question: There are $2^4=16$ distinct binary boolean operators. Two operators are regarded the same if one can be obtained from the other by exchanging the operands (input). It is easy to see only $...
2
votes
0answers
78 views

Are there any good books on propositional, first order, and second order logic that don't require me to be a supergenius?

I am trying to learn mathematical logic but every textbook I come across is so hard to read and understand, and assumes I'm already an expert in everything. Is there anything aimed at beginners that ...
2
votes
0answers
73 views

Are all prop logic wffs sentences? Why aren't there any free variables?

In propositional logic is it correct to say that all wffs are also sentences/statements? Are sentences and statements the same thing? I also read that sentences are wffs that lack free variables, but ...
2
votes
0answers
49 views

How many implication graphs are there for a given number of literals?

The context here is implication graphs over propositional literals and the 2-SAT problem. What function describes the possible number of non-redundant implication graphs given the number of literals? ...
2
votes
0answers
43 views

Help with duality and recursive definitions

I'm struggling with the following problem: Let $L_1^*$ be the language obtained from $L_1$ by removing $\to$ and $\leftrightarrow$ from the stock of connectives (leaving it with $\neg, ∧, ∨, \...
2
votes
0answers
45 views

Logical expressivity and model classes

Consider two logical languages $\mathcal L_1\subseteq\mathcal L_2$. Let the corresponding logics be semantically defined. Suppose that the correspond models depend on the language itself, but there is ...
2
votes
0answers
45 views

Can propositional calculus be written with a single rewrite rule?

I have seen some systems where propositional logic can be written by a single axiom plus an inference rule such as Nicod's axiom. This to me seems like two rewrite rules. If Nicod's axiom is $N(a,b,...
2
votes
0answers
105 views

k-CNF formulae and formulae that are not equivalent to them

I would like to understand the complexity of $k$-CNF formulae. For $k\geqslant 1$, can one please give me an example of a formula that is not equivalent to a $k$-CNF formula?
2
votes
0answers
32 views

Are there automated proof search algorithms for extended Frege systems?

Nowadays standard in automated theorem proofs are algorithms based on resolution system. There were quite a few attempts to present algorithms based on natural deduction (which is stronger than ...
2
votes
0answers
112 views

Prove this conjecture for $k = 4$ i.e. prove that whatever moves $A$ can come up with, $B$ can always reply such that, in the end, $A$ has no moves.

Two players $A$ and $B$ are playing the Eat the set game. The game is the following: • The game starts with a set $S$ of $k$ elements i.e. $S = \{1, 2, . . . , k\}.$ Players have to choose subsets of ...
2
votes
0answers
82 views

Boolean algebras as models of (quantifier-free) monadic predicate logic

Suppose we have a Boolean algebra over $n$ bits, meaning when viewed as a vector space over $F_2$, the dimension is $n$. Then we can define $n$ unary predicates $P_n$ which return the value of the $n$...
2
votes
0answers
44 views

Strength of Asymmetric Tautology/Reverse Unit Propagation in proofs

Given a set of disjunctions in propositional logic, they can be said to entail another disjunction D if the negation of D, when added as a set of unit clauses to the original set, yields an ...
2
votes
0answers
132 views

completeness of propositional logic from $(a \to b) \to ((\lnot a \to b) \to b)$

At Wikipedia/Propositional_Calculus I found the following proof sketch of the completeness of propositional logic systems which (among other things, I assume) admit the proof-by-case-analysis formula $...
2
votes
0answers
101 views

Sentential Logic. Reasoning.

can anybody critique, and if necessary, correct, my reasoning in the following translation? c. Either Alice has a dog and Carol has a cat, or Bob has a dog and Carol does not have a cat. This is ...
2
votes
0answers
4k views

Converting DNF to CNF and vice versa

I am fairly confident of the definition of CNF and DNF (e.g. why $ (P \land Q)$ in both CNF and DNF. However, I'm a little shaky when it comes to converting between the two normal forms. Is it ...
2
votes
0answers
144 views

Different ways to define Kripke structure

The Wikipedia page https://en.wikipedia.org/wiki/Kripke_structure_(model_checking)#Example has an example of a Kripke structure $M = (S,R,L)$; however, others define Kripke structures as $M = (S,R,V)$ ...
2
votes
0answers
138 views

Are these two logical statements equal?

I found this question from a website: "Neither the fox nor the lynx can catch the hare if the hare is alert and quick." Let: P: The fox can catch the hare Q: The lynx can catch the ...
2
votes
0answers
118 views

Natural deduction proof without assumption

$$(((p\iff q)\iff r)\wedge(q\iff r))\implies p$$ Should be done with natural deduction, but up to $60$ steps. If I assume $\neg\:p$ probably I may finish up to $20$ steps, but without assumption I ...
2
votes
0answers
30 views

n-formula for k n-evaluations

I am trying to solve the following problem Let $N = \{0, 1, 2, ...\} $ is the set of natural numbers. Propositional variables are $ A_{n}$ for $n \in N $ . An evaluation $v$ is called $n$-...
2
votes
0answers
124 views

Expressing schedule of reinforcement rule using mathematical logic

I am trying to formalize the rules for application of different schedules in a reinforcement learning in special education. Children learn through trials. Each trial is successful if the child ...
2
votes
0answers
158 views

Help with propositional logic

Hi all this is for a homework where we just started learning logic and I am not very familiar with propositional logic. So we have two problems: To show a proof of the Sherlock Holmes syllogism ...
1
vote
0answers
55 views

“Truth set” approach to validity and logical consequence: how does it relate to the standard approach? what are the possible drawbacks?

References : I think the " truth set approach" to validity and logical consequence can be linked to the name of R. Carnap ( who defines L-truth and L-implication in this way in his Introduction to ...
1
vote
0answers
38 views

Can we use induction on the number of connectives?

Usually when we prove some properties of propositional formulas, we use induction on the complexity of propositional formulas, but instead, we can just use induction on the number of occurrence of ...
1
vote
0answers
102 views

Proof of Validity of My Polynomial Time Algorithm for $co-NP$ Complete Problem

I posted an algorithm yesterday, that purported to solve the co-NP Complete 'Boolean Tautology Problem' in polynomial time. Link to the algorithm : polynomial time algorithm In that post, I presented ...
1
vote
0answers
39 views

why does a closed circuit represent a false proposition? (Claude Shannon thesis)

In reading through Claude Shannon's paper: A Symbolic Analysis of Relay and Switching Circuits. As a software engineer, I got confused by Shannon's choice to have 0 as representing a closed circuit, ...
1
vote
0answers
78 views

Alternative sources for a topos theory description of zeroth order logic

I have recently been reading Robert Goldblatt's fantastic book Topoi: The Categorial Analysis of Logic. Through chapters 6-8, Goldblatt produces a topos theoretic approach to zeroth order logic, where ...
1
vote
0answers
124 views

S5 proof of $\square(\square P\rightarrow\square Q)\vee\square(\square Q\rightarrow\square P)$

I'm trying to construct an S5 proof of $\vdash\square(\square P\rightarrow\square Q)\vee\square(\square Q\rightarrow\square P)$. I know that $\phi\vee\psi$ is equivalent to $\text{~}\phi\rightarrow\...
1
vote
0answers
92 views

How to prove something is not a logical consequence of 2 propositions.

I have a question where I have to show that the third statement is not a logical consequence of the 1st two using a truth table. I've seen how you'd do if there are only two (How to prove logical ...
1
vote
0answers
52 views

Does this have a name? $\vDash(a_1\to(a_2\to(\cdots(a_{n-1}\to a_{n})\cdots)))\leftrightarrow((a_1\wedge a_2\wedge\cdots\wedge a_{n-1})\to a_n)$

For all formula $\alpha_1, \alpha_2, \cdots, \alpha_n$, $$\vDash (\alpha_1\to(\alpha_2\to(\cdots(\alpha_{n-1}\to\alpha_{n})\cdots))) \leftrightarrow ((\alpha_1\wedge \alpha_2\wedge\cdots\wedge\...
1
vote
0answers
34 views

Equivalence of strings in modal logic

I'm trying to solve a question which asks me to show that for any two finite strings $O_1$ and $O_2$ of $\square$s and $\lozenge$s, (e.g. $\square\lozenge\lozenge\square\lozenge\square)$, that i) if $...
1
vote
0answers
44 views

Is this a Boolean algebra? (proof)

Let $B=\{0,1\}$ and the binary operations $\oplus,\cdot$ We define a bijection $\varphi$ s.t.: $$ \varphi:B \longrightarrow L=\{\mathbf{False},\mathbf{True}\}, $$ $$ \varphi(x):= \begin{cases} \...
1
vote
0answers
74 views

showing that $(\lnot \lnot Q) \to Q$ is not an inutionistic tautology by using an ad hoc 3-valued logic?

I'm trying to prove that $\lnot \lnot Q \to Q$ is not an intuitionistic tautology by constructing a special finitely-valued logic with strictly more tautologies than intuitonistic logic ... and then ...
1
vote
0answers
62 views

Prove that $\{ \phi \rightarrow(\psi \rightarrow \theta)\} \vdash \phi \wedge \psi \rightarrow \theta$?

Please, can you check is my solution of this problem $\{ \phi \rightarrow(\psi \rightarrow \theta)\} \vdash \phi \wedge \psi \rightarrow \theta$ good? First, I rewrote it like $\{ \phi \rightarrow(\...
1
vote
0answers
45 views

Compact witness of satisfiability of a formula in intuitionistic logic

Given a formula in intuitionistic sentential logic, there is a nice, compact textual representation for a witness of its tautology, namely a program in a typed lambda calculus with introduction and ...
1
vote
0answers
49 views

Solving Propositional Calculus

"If Jimmy takes the Math Class, Jimmy will lose his weight. If Jimmy takes the Music Class, Jimmy will lose his hair. Jimmy will take the Math Class and the Music Class. Therefore, Jimmy will ...
1
vote
0answers
36 views

Describing “at least” using logical connectives.

If s, j, and b are logical statements, how do I express the statement "s is true and at least one of the others is false"? Is it $s\wedge (\neg j \vee \neg b)$? But wouldn't there be a case for $\neg ...