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
2
votes
3answers
36 views

Negation of “Either X is true, or Y is true, but not both”

Negation of "Either X is true, or Y is true, but not both" My attempt: If seems that let X be true and Y be true, not X for X is false and not Y for Y is false. In order for the above statement to ...
2
votes
1answer
40 views

What is the intuition behind the formula $p \leftrightarrow (q \leftrightarrow (r \leftrightarrow …))$?

I cooked up the formula $p \leftrightarrow (q \leftrightarrow (r \leftrightarrow ...))$ and naively thought it is a sort of "equivalence" relation. It turns out I am wrong. Suppose you have four ...
0
votes
0answers
35 views

Is there a Hilbert-style Axiom system for Classical Propositional Logic where formulae are in negation normal form?

The wiki page (https://en.wikipedia.org/wiki/List_of_Hilbert_systems) has a list of various axiom systems for classical propositional logic (CPL), however, the page omits mention of an axiomatisation ...
1
vote
2answers
78 views

Natural deduction has me stuck

I have been trying to break down these two formula correctly using natural deduction, and now I am stuck and confused. Below there is my attempt to derive the propositional logic consequences. I need ...
1
vote
1answer
20 views

CNF and DNF form of single logical variable

I am learning boolean algebra. So apologies for this naive question. During our discussion among friends, we came across following puzzle, How can I convert following statement into CNF and DNF? $$ ...
1
vote
1answer
26 views

Negating a Statement “At least K numbers are larger than W”

What is the negation of "At least $K$ numbers are larger than $W$"? Suppose if we set $j=$ number of numbers larger than $W$. Then, $$j \ge K$$ which negates as, $$j<K$$ which translates to $$\...
0
votes
0answers
25 views

Proving first order logic in coq

I want to prove something like: Theorem new_theorem : $\forall (A B: \text{Prop}), ((A \wedge B) \iff (B \wedge A))$. in coq. I know, i could just type firstorder., but could i prove this in coq ...
9
votes
2answers
87 views

Curious tautological pattern on“p->p”

I found something that boggles me ( I'm really a beginner in symbolic logic, so maybe it's very trivial). I was practicing with truth-tables, and I found that: "p->p" is a tautology "(p->p)->p" is ...
-2
votes
0answers
29 views

With the use of resolution method decide whether this is correct. If not, provide a counter example [closed]

I am learning Logic and solving to decide if the stated formula is correct by using the resolution method. {(¬p ∨ q), (p → r)} |= r ∨ q . Below is my unsure attempt to the question. All corrections ...
2
votes
1answer
50 views

Decide whether this is correct, using the method of resolution. If not, provide a counter example.

I am new to logic and wanted to decide whether the following is correct using the method of resolution: |= p → ¬ (p → (p ∧ (p ∨ q))) My attempt to this I answered that the conclusion is incorrect, ...
3
votes
2answers
42 views

Transforming Hilbert-style Axiom Systems for Classical Propositional Logic and Retaining Soundness and Completeness

First off, I will use ~ for negation, & for conjunction, V for disjunction, -> for implication, and <-> for bi-conditional. To the question: The axioms of classical propositional logic (CPL) ...
1
vote
0answers
72 views

Meta-logic of Hilbert-style propositional calculus

I am trying to study the foundations of mathematics from the bottom-up (propositional logic then predicate logic then the axioms of set theory.) Currently, I'm considering the following Hilbert-style ...
0
votes
1answer
48 views

Quantifiers and empty set

Let $X$ and $Y$ be sets. Suposse that $X=\varnothing$ and $Y\neq \varnothing$. Is $$(\forall x\in X) (\exists y\in Y)\;p(x,y)$$ TRUE?
0
votes
1answer
16 views

Simplifying propositional logic formulas [closed]

I'm learning propositional logic, but simplifying the formulas are difficult for me... I have $P\vee Q \implies Q\wedge\neg P$. Here i am not quite sure how i should approach this. I started solving ...
1
vote
2answers
85 views

Help to find a proof in natural deduction

I have a question about the methodology of natural deduction, more specifically finding a proof in natural deduction. The assignment says: Find a proof for the formula $(P \rightarrow \neg P) \...
7
votes
3answers
407 views

Why does $AB + BC + CA = (A\oplus B)C + AB$ not imply $BC + CA = (A\oplus B)C$ in boolean algebra?

I am new to Logical Inequalities. Please bear with me if I am inexplicably stupid. The following is a Proven Equality: $$AB + BC + CA = (A\oplus B)C + AB$$ I noticed that I cannot "cancel out" $AB$ ...
2
votes
2answers
56 views

given $\neg p$ and $p\vee q$ how to use fitch system to prove $q$?

as the title says: given $\neg p$ and $p\vee q$ how to use fitch system to prove $q$? It seems like a simple thing but I can't figure out how to do it. EDIT: I understand this is a valid rule of ...
1
vote
2answers
77 views

Can one prove by lack of contradiction?

A proof by contradiction takes the form of if ~p then c, hence p. Or in other words, assume something is false, and if there is a contradiction that arises from this assumption, it must be true. Can ...
0
votes
0answers
16 views

Prove ⊢A→¬¬A in HPC proof system [duplicate]

I want to proof: ⊢ A → ¬¬A Using a system with the Modus Ponens rule, and the following axioms: A1: a → (b → a) A2: (a → (b → c)) → ((a → b) → (a → c)) A3: (¬b → ¬a) → ((¬b → a) → b) If thats ...
2
votes
1answer
35 views

Truth table and logic question

Let $p,q$ and $r$ be sentances I know that $[(p\to q)\land (p\to r)]\iff p\to(q\land r)$. (1) is true. Let $p,q,r,s,t$ be sentences Is $[(p\to q)\land (p\to r)\land (p\to s)\land (p\to t)]\iff p\to(...
0
votes
0answers
24 views

Logic question that only uses basic rule of SL: $¬(A→B) ∴ (A\land ¬B)$ [duplicate]

use only the basic rule of SL to solve this: $$\lnot (A\to B)$$ $$ \therefore (A\land ¬B) $$ Since there is a premise, how should I go from here? Can I simply change the first argument to $\lnot (\...
0
votes
1answer
44 views

Can all proof systems be generically described?

Can every proof calculus (e.g. natural deduction, Hilbert-style axiomatic systems, sequent calculus) be expressed as a generic 4-tuple {A, Ω, Z, I} consisting of: set alpha of proposition symbols, ...
0
votes
1answer
38 views

Laws of logical equivalence

How do I solve this to show that the L.H.S = R.H.S ((p → q) ∨ (¬p → r)) → (q ∨ r) ≡ q ∨ r I have to show this using the laws of logical equivalence. I have made some attempt using implication law, ...
1
vote
1answer
42 views

Why is modus ponens not an axiom?

Yes, it is a rule of inference and not an axiom. But how does it not qualify as an axiom? What specifically is the disqualifying feature?
1
vote
2answers
63 views

Construct a proof for the argument: P ∨ Q, ¬Q ∴ P

Could you please help me to complete my proof using (only) : ∧I, ⊃I, ∨I, ≡I, ∧E, ⊃E, ∨E, ≡E, ¬I and ¬E. P ∨ Q, ¬Q ∴ P I tried this proof, on http://proofs.openlogicproject.org/ : but it seems that ...
0
votes
0answers
12 views

Dual of Propositional Formula [duplicate]

I have a question regarding an older question on StackExchange, because the answers are confusing me. Duality discrete math problem How do I create the dual of a term? 1) ...
2
votes
2answers
50 views

Are inference rules just tautologically (or syntactically) valid arguments?

"An argument is valid iff the following implication is a tautology: $h_1∧h_2∧...∧h_n⇒C$ where $h_1∧h_2∧...∧h_n$ are the hypothesis and $C$ the conclusion." A classic inference rule is modus ponens ...
0
votes
2answers
56 views

Write a statement in propositional logic that says $x \in A Δ B$. Solution should use at most two connectives.

We have two sets $A$ and $B$ and some object $x$. Let’s introduce two propositional variables: $a$, which states that $x \in A$, and $b$, which states that $x \in B$. I get as far as $(a \lor b) \...
0
votes
1answer
42 views

Derivation of $\text{A} \vee \neg{\text{A}}$ without a premise.

In one of my homework problems, I need to deduce that $\text{A} \vee \neg{\text{A}}$ without a premise. The lecturer mentioned that students should "combine" answers for the previous two problems ...
4
votes
2answers
83 views

Logically, deductively, tautologically, semantically, syntactically valid arguments, what is the difference?

I've read 4 logic books in total but i'm getting crazy with all these xxxally valid argument what is the difference?? What is the difference between Logically, deductively, tautologically, ...
0
votes
1answer
24 views

finding CNF and a logically Logically equivalent DNF for Propositional form (p→(q→r)) [closed]

I can write the truth table for (p→(q→r)) but i was not able to find the required CNF and a logically Logically equivalent DNF for Propositional form (p→(q→r)) . It's confusing.
0
votes
1answer
19 views

Trichotomy and Xor - odd results

I've come across something odd. If one wants to logically formulate trichotomy the following formulation is incorrect: $$ (\alpha \oplus \beta) \oplus \gamma $$ For all WFF's being $ T$ one gets that ...
1
vote
2answers
40 views

Question about MU puzzle from GEB

In MU puzzle: https://en.wikipedia.org/wiki/MU_puzzle#The_puzzle, We have "MU" string and 4 rules. Now when compared this to logic the wiki article says "The MI string is akin to a single axiom, and ...
1
vote
1answer
27 views

Propositional and First Order Logic Tool to analyse formula

I am looking for an online tool which analyses a given propositional and/or first order logic formula. For example the tool should output, whether the given formula is satisfiable, its rank, ... If ...
0
votes
1answer
33 views

I found that resolution is not complete: what do I miss?

I am a newbie in propositional logic and I am learning by myself. I am reading the book A First Course in Logic : An Introduction to Model Theory, Proof Theory, Computability, and Complexity by Hedman....
2
votes
1answer
57 views

Proving $\vdash \neg \neg P \to P$ in first order logic, preferrably without deduction theorem

The axiom system used is $A\to B \to A$ $(A \to B \to C) \to (A \to B) \to A \to C$ $(\neg A \to \neg B)\to (B \to A)$ $(\forall x A) \to A[t/x]$, where $x$ is substitutable with $t$ in $A$. $\forall ...
0
votes
2answers
44 views

Understanding how to prove either/or type statements in logic

I've been working my way through a logic textbook and I recently came across this problem: B and D are statement forms such that B → D is a tautology. Now, if b and d have no statement letters in ...
0
votes
3answers
36 views

I want to prove $P$ is true (by contradiction). What happens if I deduce $Q$ from $\lnot P$, knowing $\lnot Q$, then replace $Q$ with $P$?

I have a quick question about reasoning by contradiction. Suppose I want to prove that a proposition $P$ is true (by contradiction). I will suppose that $\neg P$ is true and I will try to deduce that ...
-2
votes
1answer
42 views

Help, have to prove the tautology (p ∨ ¬p) from nothing using fitch system. [closed]

I'm new using fitch so this is all i have and don't know how to get it done. (https://i.paste.pics/d0746642a4513e1ca1799b3e92e2ace2.png) Here's the link of the exercise: http://intrologic.stanford....
5
votes
1answer
85 views

Proof Verification: Special Case of Compactness Theorem For Classical Logic.

I'm trying to prove a special case of the compactness theorem. Here is a statement of the compactness theorem in this handout. A set of formulas $\Phi$ is satisfiable iff it is finitely satisfiable....
0
votes
2answers
36 views

Assumption in the proof of completeness theorem in Sentential Calculus

I have a problem understanding the Completeness Theorem in Sentential Calculus, which appears in the Merrie Bergmann's The Logic Book 4th edition. The theorem states that if P is a logical consequence ...
1
vote
1answer
59 views

Urgent Help Given p ⇒ q, use the Fitch System to prove ¬q ⇒ ¬p. [closed]

I think I'm close but I don't know what to do next. Help, please. All I've done is this: 1.p=>q Premise 2.~q assumption 3.p assumption 4.q implication elimination 1,3 5.q&~q and ...
2
votes
0answers
23 views

Karnaugh maps for resolution in propositional logic

Are Karnaugh maps "good enough" or mathematically acceptable to prove a CNF formula can't be satisfied instead of using propositional logic resolution? This method also shows all possibilities to ...
1
vote
1answer
26 views

How to check if sets of clauses are satisfiable.

I do not know how to check if the sets of clauses are satisfiable in an efficient way. Consider I have these sets for which I need to to check satisfiability. How do I do it efficiently without taking ...
0
votes
1answer
21 views

Can we resolve two variables at a time in CNF resolution

Are we allowed to resolve two variables at a time in CNF resolution? For e.g. we have: what will be the resolution of: $(P \lor \lnot Q \lor R) \land (\lnot P \lor Q \lor R)$ and what will be the ...
0
votes
0answers
56 views

completeness proof propositional logic Chiswell and Hodges´ book

I have a doubt about the completeness proof of propositional logic that appears in Chiswell and Hodges´ book. In page 93, case 2, i) I don´t understand why I can replace χ_1 by χ_1 and χ_2, because I ...
6
votes
2answers
113 views

$ \models A$ vs. $ A \models$

As I understand it, $ \models A$ means $A$ is a semantic consequence of the empty set. So the "empty space" on the left side of the double turnstile means "empty set". However, when we take a look ...
2
votes
2answers
49 views

Basics of Set Theory : complement of an intersection.

My maths textbook says, 1) If x ∉ (A∩B) => x ∉ A or x ∉ B 2) If, A = {x:x is divisible by 3 and 5} => A' = {x:x is not divisible by 3 or x is not divisible by 5} The italicised parts ...
0
votes
1answer
22 views

The $\text{NOR}$ operation is defined at follows $x \text{NOR} y = \text{NOT}(x+y)$. How do I prove that $\{\text{NOR}\}$ is functionally complete? [duplicate]

The $\text{NOR}$ operation is defined at follows $x\;\text{NOR}\;y = \text{NOT}(x+y)$. How do I prove that $\{\text{NOR}\}$ is functionally complete? I need help solving it as I don't know how to.
0
votes
2answers
47 views

Can the statements about future be proposition?

i am confused with not happened statement whether they are proposition or not.For example , if i say that "tomorrow there will be an earthquake in Canada".Can we say that it is a proposition because ...

1
2 3 4 5
83