# 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,588 questions
Filter by
Sorted by
Tagged with
72 views

### Simple logic question $∀a ∈ A, [(∃b ∈B : P(a,b)) \Rightarrow Q(a)]$ [closed]

I have a question about the logic coming from a proof I was working on, which I thought of generalizing with these two propositions. I am seeking help because I cannot understand whether the two ...
133 views

### Prove $(B \implies (C \implies D)) \implies (C \implies (B \implies D))$ without the Deduction Theorem

I am reading "Introduction to Mathematical Logic" by Elliott Mendelson, and I am currently at the axiomization of propositional calculus. Mendelson presents the following three axioms (with ...
• 23
20 views

### Compactness theorem of propositional logic and the Ramsey Theorem

Are there any modern references (books, articles) about connection of compactness theorem of propositional logic and the Ramsey Theorem? Thanks.
49 views

66 views

### Example of undecidable recursive set of formulas in Propositional Logic

Context In first order logic, we study a lot various undecidable theories like Robinson arithmetic or Peano arithmetic. I was wondering what is there to study in the field of (un)decidability in the ...
1 vote
65 views

• 79
38 views

### Categoriсal perspective on the Disjuntion property of the intuitionistic propositional calculus

I came about four different proofs of the disjunction property: formulated in the language of Heyting algebras; done using Kripke models; using the fact that every topological space is an open ...
• 88
84 views

• 1,383
247 views

### Why is exclusive disjunction not a standard logical operation?

This question Rules of inference for exclusive disjunction and logical biconditional shows that the inference rule for exclusive disjunction are little different from the other rules for conjunction, ...
185 views

### Understanding a proof in propositional logic

I would like help understanding two related claims being made in the following proof, found in the fourth edition of Elliot Mendelson’s introduction to mathematical logic, which I am reading on my own ...
• 501
1 vote
112 views

### Necessity of universal quantifier to represent a theorem with logic symbols

I have a preference to reduce the proof steps of a theorem, and the theorem itself, into logic symbols as much as possible. Not just because it is aesthetically appealing, but because it makes makes ...
• 19
40 views

### Null Quantification Rosen's Discrete Math Textbook Exercise Confusion/Clarification

From Discrete Math Rosen textbook 8th edition Section 1.4 Exercises: Exercise 48-51 establish rules for null quantification that we can use when a quantified variable does not appear in part of a ...
• 883
47 views

### Clarification on logical equivalence, bi-conditionals, and operators [duplicate]

What are the differences between $<-->$ vs $\iff$ vs $\equiv$ in terms of biconditionals and logical equivalence? Kindly please let me know :)
• 883
48 views

### Clarification on logical equivalence [duplicate]

So is this correct to say that 2 + 2 = 4 ≡ 3 + 2 = 5, since both are true statements? It's a simple question but usually when logical equivalence is mentioned it's mostly seen between two propositions ...
• 883
49 views

### How to translate formally this sentence with 'and, not, or'?

Let p, q, and r be the propositions “The package was delivered on time,” “The package was damaged during transit,” and “The customer received the correct item,” respectively. How will the sentence “...
31 views

Screenshot from Discrete Math Rosen Textbook. Note that the restriction of a universal quantification is the same as the universal quantification of a conditional statement. For instance, ∀x < 0 ($... • 883 0 votes 1 answer 33 views ### Free Variables in Quantified Proposition (from Discrete Math Rosen Textbook) I'm just confused 2 things: Based on what I underlined in red, would the statement (also underlined in red) "there exists an x such that x + y = 1" (I'll assume domain of discourse for x ... • 883 8 votes 4 answers 1k views ### Confusion on using "unless" more than once in proposition I'm having trouble interpreting this highlighted sentence (from Discrete Math Rosen Textbook) properly due to using unless more than once in this sentence. I understand that q unless (not p) is the ... • 883 0 votes 2 answers 72 views ### Trying to understand how numbers themselves (s0, ss0, sss0, etc) are represented in Gödel numbering Problem solved: I did not actually read the table given on page 70 of nagel and newman. s does have a Godel number. It's 7. So ss0 would be broken down into 7, 7, and 6, since 0 is given the number 6. ... 0 votes 0 answers 45 views ### Validate proof for$A \Rightarrow B, (C \vee \neg A) \Rightarrow F, B \Rightarrow D, \neg D \vDash F$I have the following premises: $$A \Rightarrow B, (C \vee \neg A) \Rightarrow F, B \Rightarrow D, \neg D$$ I attempted to construct a proof for the conclusion$F$using inference rules, but I'm not ... • 194 0 votes 1 answer 67 views ### Really lost on how propositions Q4 and Q5 were derived: n-Queen problem Discrete Math Rosen Textbook The context is the well-known n-Queens problem and on the textbook, the following compound proposition is given: Let$p(i,j)$be a proposition that is$True$iff there's a queen in the$i$th row and$...
• 883
1 vote
Suppose we only have all the standard left and right logical inference rules ($∧L_{1}$, $∧L_{2}$, $∨L$, $→L$, $¬L$, $∨R_{1}$, $∨R_{2}$, $∧R$, $→R$, $¬R$) and on top of that 4 quantifer rules (see the ...