Skip to main content

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

Filter by
Sorted by
Tagged with
-1 votes
2 answers
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 ...
user avatar
2 votes
1 answer
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 ...
gestory2's user avatar
0 votes
0 answers
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.
Rustam Mamin's user avatar
0 votes
0 answers
49 views

Is there a propositional proof system that is not known to be simulated by extended Frege? [closed]

Extended Frege is a propositional proof system that is achieved by adding the extension rule to a Frege system. That rule allows to replace formulas with fresh variables. A propositional proof system $...
rus9384's user avatar
  • 411
1 vote
3 answers
150 views

Proving the Negation of a Formula does not Require the Formula as an Assumption

The following lemma states that if we can prove negation of a Well Formed Formula (WFF) $\alpha$ by assuming the formula itself, then we can do it without such an assumption. Lemma. Let $\Sigma$ be a ...
Hosein Rahnama's user avatar
0 votes
1 answer
29 views

Confusion about Proving the Uniqueness of Linear Representation in N-ary Boolean function

$f\in B_n$ is called linear if $f(x_1,\cdots, x_n)=a_0+a_1x_1+\cdots+a_nx_n$ for suitable coefficients $a_0,\cdots, a_n\in \{0,1\}.$ Here $+$ denotes exclusive disjunction (addition modulo 2) and the ...
Yinuo An's user avatar
  • 370
0 votes
2 answers
81 views

Constructing a proposition in propositional logic which is a tautology if and only if ...

I'm trying to solve the following question: Let $A=\left \{ a_1,..,a_n \right \}$ be a finite set of arbitrary elements and $B_1,...,B_m$ subsets of A. Let $k\leq m$ be a natural number. Write a ...
Daniel's user avatar
  • 83
2 votes
1 answer
118 views

Is a propositional function a proposition in propositional logic?

In mathematical logic, a proposition is defined as a declarative sentence that is either true or false, but not both. Two examples are '1 + 1 = 2' and 'Paris is the capital of France'. I have noticed ...
Dr. J's user avatar
  • 149
1 vote
4 answers
157 views

Symbolising an following argument with two Therefore's

I am trying to translate the following argument to logic symbols to verify its validity using truth tables: If the supplier supplies the seeds, then if the seeds are sown on time, then the plants ...
Trascendence's user avatar
2 votes
1 answer
54 views

Last Bits of Proof of the Compactness Theorem in Propositional Logic

I am reading the proof of compactness theorem for the propositional logic and the last part of the proof is left as exercise 2 of section 1.7 in the book by Enderton, A Mathematical Introduction to ...
Hosein Rahnama's user avatar
1 vote
1 answer
67 views

What is a statement in Chiswell & Hodges Mathematical Logic?

I am beginning to read Mathematical Logic by Chiswell and Hodges. In Chapter 2 Informal Natural Deduction, the authors don’t give a definition of statement. They say to use a test. I’m confused why ...
Dr. J's user avatar
  • 149
0 votes
0 answers
49 views

Proof of ((A→B)→A)→A using axioms and hypothetical syllogism

Problem: Prove ( ( 𝐴 → 𝐵 ) → 𝐴 ) → 𝐴 ((A→B)→A)→A using axioms and hypothetical syllogism (HS). Relevant Axioms: Axiom 1 (A1): 𝐴 → ( 𝐵 → 𝐴 ) Axiom 2 (A2): ( 𝐴 → ( 𝐵 → 𝐶 ) ) → ( ( 𝐴 → 𝐵 ) → (...
daniel ph's user avatar
3 votes
2 answers
69 views

Predicate formula of proposition, author lacks precision in explanations

I have a problem: Consider the two following propositions: All persons have a mother. There is one mother of all persons. Now consider the predicate formulas of both propositions: $\forall x \...
Noah Wurtz's user avatar
-1 votes
1 answer
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 ...
kevin.spacey's user avatar
1 vote
1 answer
65 views

Using contradiction to validate an argument

In general, when we want to establish the validity of the argument $(p_1 \land p_2 \land ... p_n ) \rightarrow q$, we can establish the validity of the logically equivalent argument $(p_1 \land p_2 \...
user avatar
0 votes
0 answers
112 views

Why can't three-valued logic (ternary logic) simply have only two truth values?

Consider the statement: P ∧ ¬P ⊢ Q where: P is any proposition. -¬P is the negation of P. Q is another proposition. Wouldn't proving both P and ¬P to be true simply lead to a new proposition Q, ...
Sam's user avatar
  • 9
0 votes
0 answers
34 views

A generalized algorithm to convert a formula in algebraic normal form to an equivalent formula that minimizes the number of bitwise operations

In this question, “bitwise operation” means any operation from the set {XOR, AND, OR}. The NOT operation is not included because ...
lyrically wicked's user avatar
0 votes
0 answers
62 views

Would this logic be considered constructive?

I have asked about similar logics before, but this one is different. The logics that I’ve asked about in the past take the Gödel-McKinsey-Tarski translation for Intuitionistic Propositional Logic to ...
PW_246's user avatar
  • 1,383
2 votes
1 answer
41 views

Understanding a proof of the completeness Theorem for Propositional Resolution.

I'm having trouble understanding the proof of 1.3.4., the Completeness Theorem for Propositional Resolution in this book. The main portion of the proof goes like this: Given a (finite) set of clauses ...
Knogger's user avatar
  • 229
0 votes
0 answers
45 views

Propositional calculus - variable assignment proof

I am having trouble to formally prove the following: let α,β,γ be well formed formulas. prove that if Var(α) ∩ (Var(β) ∪ Var(γ)) = ∅ and β(α/p1)=γ(α/p1) then β=γ It would be great to get some ...
yaniv tzipin's user avatar
-1 votes
1 answer
36 views

Given a formula how can we figure out if it is CNF or DNF

Can anyone please help me understand if the following formulas are DNF, CNF, both CNF and DNF, and neither CNF nor DNF? From my understanding, CNF is a conjunction of disjunction literals and DNF is a ...
Super Code's user avatar
2 votes
1 answer
35 views

Generate as short as possible boolean formula from a given truth table

Given a truth table, maybe 3-vars, 5-vars or even 10-vars, i can write its formula in DNF or CNF, and simplify it using K-Map or Quine-McCluskey algorithm. But it is based on {NOT, AND, OR}. Now the ...
tangsongxiaoba's user avatar
0 votes
1 answer
72 views

Confusion on Question from Kenneth Discrete Math Textbook

Suppose there are signs on the doors to two rooms. The sign on the first door reads “In this room there is a lady, and in the other one there is a tiger”; and the sign on the second door reads “In one ...
Bob Marley's user avatar
1 vote
1 answer
93 views

Substituting propositional variables given a true biconditional

Say I know that $p ↔ q$ AND $q ↔ (p ∧ ¬q) ∨ (¬p ∧ q)$ are both true. From hypothetical syllogism, the logical equivalence $(x → y) ∧ (x → z) ≡ x → (y ∧ z),$ and the simplification $(x ∧ y→ y$ is a ...
Bob Marley's user avatar
2 votes
2 answers
94 views

Proving (p → r) ∨ (q → r) ≡ (p ∧ q) → r

So I do understand that this could be much more easily proven using basic logical equivalences as follows: (p → r) ∨ (q → r) ≡ (¬p ∨ r) ∨ (¬q ∨ r) ≡ (¬p ∨ ¬q) ∨ r ≡ ¬(p ∧ q) ∨ r ≡ (p ∧ q) → r However, ...
Bob Marley's user avatar
0 votes
0 answers
44 views

Question regarding two beginner inductive hypothesis proofs in Propositional Logic

I am currently studying the semantics of PL, and there are two exercises in the book that ask me to prove the following by induction: Show that for every $n \geq 0$: $(A_1 \wedge, A_2 \wedge, ..., \...
Kliker's user avatar
  • 79
0 votes
0 answers
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 ...
Georgii's user avatar
  • 88
0 votes
2 answers
84 views

Showing equivalence between two definitions for Maximal ideals

Background: Definition 1: Let $R$ be a ring and $M$ be an ideal of $R$. Then $M$ is called a maximal ideal of $R$ if $M\neq R$ and there does not exist any ideal $I$ of $R$ such that $M\subset I\...
Seth's user avatar
  • 3,683
1 vote
0 answers
55 views

Is this combination of Lukasiewicz proof systems complete?

I’ve been learning more about axiomatic systems, and somewhat recently came across the following axiomatization for Classical Propositional Calculus a la Lukasiewicz: $(A \to B) \to (B \to C) \to A \...
PW_246's user avatar
  • 1,383
2 votes
1 answer
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, ...
user avatar
2 votes
1 answer
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 ...
Joa's user avatar
  • 501
1 vote
2 answers
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 ...
Davi1399's user avatar
0 votes
1 answer
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 ...
Bob Marley's user avatar
-3 votes
2 answers
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 :)
Bob Marley's user avatar
0 votes
1 answer
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 ...
Bob Marley's user avatar
0 votes
0 answers
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 “...
Vince Michael Lasam's user avatar
0 votes
1 answer
31 views

Quantifiers with restricted domain

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 ($...
Bob Marley's user avatar
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 ...
Bob Marley's user avatar
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 ...
Bob Marley's user avatar
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. ...
Devery Sheridan's user avatar
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 ...
pmu2022's user avatar
  • 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 $...
Bob Marley's user avatar
1 vote
0 answers
45 views

Why can't we derive the Left Contraction Rule in predicate logic?

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 ...
Alessandra12342's user avatar
0 votes
2 answers
79 views

Using equivalence of quantifiers to show $\bigcap_{f\in {\bigcup_{\alpha\in I}S_{\alpha}}}V(f)=\bigcap_{\alpha\in I}\bigcap_{f\in S_{\alpha}}V(f)$

Background Quantifier distribution and negation laws $\forall x(P(x)\wedge Q(x))=\forall xP(x)\wedge \forall xQ(x)$ $\exists y(P(y)\vee Q(y))=\exists yP(y) \vee \exists yQ(y)$ $\sim (\forall x P(x))=\...
Seth's user avatar
  • 3,683
1 vote
1 answer
77 views

Confusion on Section 1.2 of Rosen's Discrete Math Textbook

So I was able to deduce based on the rule that p implies q is the same as q unless (not p) that this is same as: (not s) -> (r -> (not q)) I could use the logical equivalence (A -> B) = (A or ...
Bob Marley's user avatar
0 votes
0 answers
45 views

Can any finite set of binary sequences be expressed as CNF/DNF

I am new to logic and cannot figure out if there are instances when a given set of binary sequences of equal length is not possible to express as a conjunctive or disjunctive normal form. If such sets ...
MsTais's user avatar
  • 397
-1 votes
1 answer
86 views

Prove that if there is a necessary condition for P that is not also a sufficient condition for P then there is more than one necessary condition for P

I am looking for verification of the below proof. I'm specifically unsure of the (Q OR P) part Claim: If Q is a necessary condition for P and Q is not a sufficient condition for P, then there is a ...
user2159306's user avatar
5 votes
2 answers
404 views

Prenex Normal Form of a Simple Proposition Reads Strangely.

I was trying to convert a simple (true) proposition concerning the real numbers to Prenex Normal Form but arrived at a logical statement that didn't appear equivalent to what I started with. The ...
eliza1024's user avatar
3 votes
2 answers
155 views

Confusion on reading multiple ways of p implies q

So these are the different ways of expressing the conditional statement, and I got these from Rosen's Discrete Math Textbook: So I want to be clear on a couple of things: When we read all these ...
Bob Marley's user avatar
-1 votes
3 answers
103 views

If $P$ and $Q$ are two propositions, then what can be said about the expression $(P \wedge(P \to Q)) \to Q$

The question If $P$ and $Q$ are two propositions, then what can be said about the expression $(P \wedge(P \to Q)) \to Q$. 1.) always true 2.) always false 3.) true for only one assignment 4.) false ...
Debu's user avatar
  • 1

1
2 3 4 5
112