# 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).

5,041 questions
Filter by
Sorted by
Tagged with
1 vote
34 views

### Showing Euclid's Proposition 30 ("Lines parallel to the same line are parallel to each other") is equivalent to the 5th Postulate.

I am trying to show that the 30th Euclid's proposition, "Straight lines parallel to the same straight line are also parallel to one another." is equivalent to the 5th Postulate: "If ...
63 views

### $A$ says "I am a knight" and $B$ says "$A$ is a Knave?" therefore what is $A$ and $B$?

$A$ says "I am a knight" and $B$ says "$A$ is a Knave?" therefore what is $A$ and $B$ ? The logic is Knights always tell the truth and Knaves always lie. What I'm thinking is ...
56 views

### How do I translate the following sentences from English to predicate logic? [closed]

The thief is only liable if they saw him enter the tunnel and found the stolen item in his possession. If witnesses see him enter the tunnel and the stolen object is not found in his possession, then ...
46 views

### Does Every Axiom Set For Classical Propositional Calculus Have Two Negations, and If So, Why?

Every axiom set for classical propositional calculus (under uniform substitution and detachment) with a conditional and negation connective that I've seen has at least two negation symbols in it (and ...
1 vote
49 views

10 views

### Czelakowski matrix semantics vs ordinary matrix semantics vs Co-Czelakowski matrix semantics

The kind of matrix semantics that I'm accustomed to seeing is something like $\langle A, F \rangle$ where $A$ is an algebra in some signature and $F$ is a subset of the carrier of $A$. A Czelakowski ...
27 views

### Prove that ⊢(¬p→q)→(¬(¬q→s)→p) [closed]

First I checked that the formula is a Tautology then I used the deduction theorem : so we only need to prove that : {(¬p→q),¬(¬q→s)}⊢p. I tried proving it using DS but failed , can someone help ?
28 views

### Need help constructing a proof tree (or truth tree) for the following argument symbolized in predicate logic.

For context, I am a logic simpleton studying for an exam in a graduate-level introduction to symbolic logic. One of the techniques I'm expected to know is constructing proof trees to test the validity ...
40 views

### Definition of a protoalgebraic deductive system

I'm trying to understand the definition of a protoalgebraic logic given in Blok and Pigozzi. I'm specifically interested in two things: Exactly which family of Leibniz operators the authors are ...
19 views

### Proof of the Local Deduction Theorem, for one of many logics

(I also asked this in MathOverflow) I'm looking for a proof of the Local Deduction Theorem for any one of many logics. That is, a proof of the statement: $\Sigma \bigcup \{\phi\} \models \psi$ iff for ...
24 views

116 views

42 views

### How to prove (P v Q) ┠ ¬( ¬P & ¬Q) with limited Rules?

I come here in time of need, as due to the plague, I was unable to attend a lesson, but need to complete the following task: Prove the following with only MTP(Modus tollendo ponens) and the ...
1 vote
92 views

### Proof by contradiction to show irrationality of $\sqrt{2}$ logically

I am trying to learn more about basic logic in order to make my proofs and reasoning more precise or even "mechanical". Just to make sure that my proof really shows what I wanted. (Any ...
143 views

### Using the Compactness Theorem for Propositional Logic to prove that the countable union of countable sets is countable

Consider a disjoint family $\{A_{n}\}_{n\in\mathbb{N}}$ of countable sets, let $A$ denote the their union. We can define a language $L$ to have atoms $p_{an}$ for each $a\in A$ and $n\in\mathbb{N}$ (...
32 views

### Proof of Completeness Theorem in Enderton's Logic, satisfiability of Γ∪Θ∪Λ

I have similar question with this post Proof of Completeness Theorem in Enderton's Logic, satisfiability of Γ∪Θ∪Λ, so I quote some of his/her description: I'm reading the proof of the Completeness ...
38 views

### Question About The Validity of An Argument

I have been reading and doing exercises form the book How to Prove It: A Structured Approach until I have reached section 1.2. I have come across the definition of a valid argument: An argument is a ...
89 views

### A natural deduction proof of $\neg (A \leftrightarrow \neg A )$.

I want to prove $\neg (A \leftrightarrow \neg A )$ in natural deduction: I tried first But I can't figure how to discharge the hypothesis $A$ and $\neg A$. I then tried Here I just need to ...
I have to prove $$(\lnot(a\land b) \land (b \lor c)\land(c\rightarrow d)) \Rightarrow (a \rightarrow d)$$ So far I have done this: $$\lnot (a\land b)\land (b\lor c)\land (c\rightarrow d)$$ $$\iff (\... 0 votes 0 answers 45 views ### A natural deduction proof of \neg (A \wedge B) \rightarrow (A \rightarrow \neg B) without RAA I am doing (for fun) the exercices of this lean tutorial. For the third exercice of section 3.6. Exercises: "Give a natural deduction proof of \neg (A \wedge B) \rightarrow (A \rightarrow \neg ... 0 votes 0 answers 49 views ### Is the "parallel axiom" sentence, a proposition in absolute geometry? I will try to explain in other words. Given a formal theory of absolute geometry, we are able to write the expression whose meaning is the paralel axiom. The question is, that expression is a "... 1 vote 0 answers 79 views ### Is it correct to judiciously construct a quantifier tableau to yield a desired falsification of a formula, yet the rules to apply weren't exhausted? I am a beginner in logic, which I am learning on my own. I am aware of the fact that a quantifier tableau with open branches doesn’t always show the formula under consideration is falsified- unless ... 0 votes 2 answers 81 views ### New Proof System I've been going on past homework and I've faced a question that seems a little bit illogical to me or that it's too simple. Here is the question: Question: Let N be a new semantic proof system which ... 6 votes 1 answer 117 views ### Proving (disproving?) a statement when its condition is not satisfied Consider the following implication. Let k\in \mathbb{Z}. If k^{2} + 5k is odd, then k^{2}+5k+1 is odd. At first it seems to be false, and one could proceed easily to prove it false directly by ... 0 votes 1 answer 48 views ### How can I show that  \{A \to B, B \to C \} \vdash A \to C  without using deduction theorem in hilbert-style system?? [duplicate] I've been confused with that for a few days. The axiomatic system is: α→(β→α) α→(β→γ)→((α→β)→(α→γ)) (¬β→¬α)→(α→β) 1 vote 0 answers 26 views ### Completeness of n-(finitely)-Valued Gödel Logic w.r.t IPC+Linearity+F_n n-Valued Gödel Logic is apparently complete with respect to IPC with the added axioms of Linearity: (A \rightarrow B) \lor (B \rightarrow A) and F_n: \bigvee_{1 \leq i < j \leq n} (A_i \... 0 votes 1 answer 67 views ### How to prove that P_b \leftrightarrow (P_a \land P_b), P_a \leftrightarrow \neg P_b \vdash P_a with natural deduction I need to build a proof for P_b \leftrightarrow (P_a \land P_b), P_a \leftrightarrow \neg P_b \vdash P_a with natural deduction... I have built the following proof, however I am stuck in the middle ... 1 vote 1 answer 47 views ### Propositional Interpolation Theorem In Fundamentals of Mathematical Logic by Hinman, page 40, there is the following exercise, rewritten in my own notation: Let S be the set of all propositions. For \phi \in S, let P_\phi be the ... 0 votes 0 answers 16 views ### Finitely Valued Multi-Valued Logic only has finitely many strengthening I was reading Kurt Gödel Collected Works by Feferman, and in the introductory note to Godel's 1932 paper A.S. Troelstra states that ''it is not difficult to show that any propositional logic ... 1 vote 0 answers 65 views ### Using the Calculus of Constructions as a metalogic Usually the Calculus of Construction is used via the Curry-Howard isomorphism, which makes it equivalent to intuitionistic first order logic. But what I am interested in is to use CoC as a metalogic ... 0 votes 1 answer 35 views ### What does it mean for propositions to be in parenthesis without logical operators. i have stumbled upon this on one of my schools automatized tests. In my universities discrete math 1 module: "Let P and Q be logic expressions, applying the laws of calculus prove the following:&... 3 votes 0 answers 65 views ### Where's the difference between \vDash and \Rightarrow? [duplicate] I'm sorry if that question has already been asked. Sometimes in propositional logic when proving "\phi \rightarrow \psi is a tautology" using truth tables people write \psi \Rightarrow \... 0 votes 0 answers 24 views ### Converting First-Order Logic to CNF I am having a lot of trouble using the rules of converting First-Order Logic to CNF. I have this statement: ∀x∃y : ([P(x, y) → Q(y, x)] ∧ [Q(y, x) → S(x, y)]) → ∃x∀y : [P(x, y) → S(x, y)] After ... 0 votes 1 answer 44 views ### Is (A \land B) a form of (p \land p)? This question is related to my previous question on forms of statements, here: Rigorous definition of the set of forms of a propositional formula. Consider the propositional formula (p \land p), ... 1 vote 2 answers 84 views ### Missteps in deriving a conclusion from premises The problem is to show that q \rightarrow r is a conclusion of the premises$$(p\wedge t) \rightarrow (r \vee s),\\q \rightarrow (u \wedge t),\\u \rightarrow p,\\\neg s. Why is the following ...
Suppose that there are $n$ premises, say $p_1,\cdots, p_n$. Then, is it possible to obtain two different conclusion? That is, Can we obtain two conclusions $q_1$ and $q_2$ using the rule of inferences ...