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).
3,630
questions
2
votes
1answer
26 views
Precedence between implication and bi-implication
I came across this question:
Let p, q, and r be the propositions
...
1
vote
1answer
24 views
How to determine if given function is functionally complete
Given any random boolean function, is their any step wise procedure to find out whether it is functionally complete?
The simplest approach I came across is this:
We need to find whether given ...
1
vote
1answer
34 views
𝛾-rule in semantic tableaux of first-order logic
I'm a novice and I'm trying to understand semantic tableaux in First-Order Logic.
𝛿 - existential rule makes sense to me, if ∃x A(x) is true, saying "let c by ...
0
votes
2answers
33 views
Problem with formulating the negation of a statement
The excersise asks us to prove with an Indirect Proof that if $abc$ is an irrational number then at most two of $a,b,c$ are rational numbers.
So we have,
Let $P$ denote "$abc$ is irrational" and let ...
0
votes
2answers
37 views
First Order Logic: Diffrence b/w $\{\forall x P(x) \implies Q(x) \}$ and $\{ (\forall x P(x)) \implies Q(x)) \}$
There is GATE exam question which is confusing (in first look at least to solve):
Which of the following first order formula is logically valid? Here
$\alpha(x)$ is a first order formula with ...
2
votes
1answer
40 views
Interpretation of a valuation function when we have a known truth and an assumed truth in a proof
To provide context, I am currently learning about Conditional Introduction. This is the first time in this propositional calculus unit that I have encountered an assumed truth ; previously, all ...
1
vote
1answer
45 views
Trying to figure out how to use “proof related notations” correctly
Let $a$ and $b$ be positive numbers. Prove that $a+b=1$ if and only if $a=2t/(1+t) $ and $b=(1-t)/(1+t)$ for some number $t$, $0<t<1$.
My Proof:
Let $P$ denote: "$a=2t/(1+t) $ and $b=(1-t)/(1+...
1
vote
1answer
22 views
NEGATE this statement: if $L(M) = \emptyset$, then for any $w$, $M$ halts on $w$ implies $M$ loops on $ww$
if $L(M) = \emptyset$, then for any $w$, $M$ halts on $w$ implies $M$ loops on $ww$
M is a turing machine.
my attempt
First I'm trying to simplify this using $A \to B = not A \lor B$
$\...
3
votes
1answer
45 views
Reference for normalization of propositional logic natural deduction.
I'm looking for a reference for the normalization of classical propositional logic natural deduction. I have heard that D.Prawitz's book Natural Deduction is a good reference on the FOL. But first I ...
1
vote
0answers
35 views
Expression deduction algorithm in propositional logic
I need to find a way to deduce an expression in propositional logic.
The given expression $\alpha$ contains up to $3$ variables.
I need to find a list of hypotheses $\Gamma$ consisting only of ...
1
vote
1answer
40 views
Is the set of Valuation Functions finite?
I've been learning about interpretation functions and valuation functions. Intuitively, it seems as though there are an infinite number of Interpretation Functions, which I will denote as $I_n$.
i.e....
0
votes
2answers
66 views
Natural deduction proof of $p \lor (p\implies q)$ with propositional calculus [closed]
I'm having a bit of trouble proving this with the propositional calculus rules.
$$p \lor (p\implies q)$$
Would someone mind helping me and showing which rules they've used with an explanation! Thanks!...
0
votes
2answers
72 views
How to prove the distributive law for propositional logic without using truth tables or natural deduction.
I haven't learnt natural deduction yet so I'm completely stuck on how to proceed. One tip I was given was to use the properties of negation but again, that's not really helping.
2
votes
1answer
72 views
First-Order Logic: Formalisation of the phrase “Not all that glitters is gold”
I am trying to determine which of the following expressions are a valid formalisation of the phrase "Not all that glitters is gold". I have the following options:
(1) ∃x. (𝖦𝗅𝗂𝗍𝗍𝖾𝗋(x)→𝖦𝗈𝗅𝖽(...
-1
votes
0answers
23 views
For what quantifiers will the statement (quantifier) x ∈ X : (quantifier) x ∈ X : P = (quantifier) x ∈ X : P be true?
For what quantifiers will the statement (quantifier) x ∈ X : (quantifier) x ∈ X : P =
(quantifier) x ∈ X : P ? Is this true by derivation, or must this be an axiom? $$ $$
For example: $ $ $\forall x ...
1
vote
1answer
30 views
Defining Deductive Validity
I read the following:
"The argument is deductively valid iff it is impossible for the all of the premises to be true and the conclusion false"
Definitions like these strike me as describing what ...
6
votes
3answers
279 views
How does one visualize propositional logic?
I apologize if this is an under specified question, but I will try and provide some context. I am beginning to learn the foundations of propositional and predicate logic after starting a course in ...
2
votes
2answers
65 views
Compactness theorem for sentential logic
I am reading proof of compactness theorem for sentential logic in Enderton's book, A mathematical introduction to logic.
(Compactness theorem) A set of wffs is satisfiable iff every finite subset ...
2
votes
0answers
52 views
Circular Induction
Question: Suppose you have
a circle with equal numbers of 0’s and 1’s on it’s boundary, there is
some point I can start at such that if and travel clockwise around the
boundary from that point, I will ...
0
votes
1answer
34 views
Conversion of English Sentence into First Order Logic & Proof using rules of inference.
I am solving some problems from the book Discrete Mathematics & its applications with combinatorics & Graph Theory by Kenneth H Rosen.
I have difficulty solving these three problems:
Is the ...
1
vote
1answer
36 views
Reference: Beth Trees in Propositional Logic
I am looking for a reference on so-called ''Beth trees''.
Take a finite set of propositional formulas $\mathcal{F}$. As an example, we might be looking for the set of valuations $v$ that satisfy ...
3
votes
1answer
84 views
Propositional Logic and Redundancy
There are Philosophical problems with the Material conditional.
The Dutch philosopher Emanuel Rutten has written an article about it, titled:
Dissolving the Scandal of Propositional Logic?
From that ...
0
votes
1answer
68 views
How to know when every conclusion has been derived from a set of statements?
Let us say that we have 3 statements:
1. A>B
2. B>C
3.A
From here, a total of 3 conclusions can be reached:
...
0
votes
1answer
49 views
Difference between $\exists x ( f(x) \rightarrow g(x) )$ and $\exists x ( f(x) \land g(x) )$?
For converting english statements to logical statements, I've understood that $\forall$ uses $\rightarrow$ and $\exists$ uses $\land$ (generally). I referred a particular question on this site, but I ...
3
votes
3answers
79 views
Is $\exists x P(x) \implies \exists x Q(x)$ Logical equivalent to $\exists x [P(x) \implies Q(x)]$
Is $\exists x P(x) \implies \exists x Q(x)$ Logical equivalent to $\exists x [P(x) \implies Q(x)]$?
My intuition:
Let Left hand side be $\exists x P(x) \implies \exists x Q(x)$ and Right hand ...
0
votes
2answers
24 views
Doubt in logical equivalence
I am beginner in mathematical logic. There is a statement in textbook(Discrete maths by Rosen) that for logical equivalence of 2 predicates, we need to show that both have same truth values(same true ...
2
votes
1answer
69 views
Doubt in logic theory [closed]
I am a beginner in mathematical logic. I found following which i did not understand
1) Addition logical implicative -
$p \to (p \lor q)$
In explanation, he says if we know p, then we can add q. ...
0
votes
0answers
18 views
Algorithm to decide whether a proposition is constructively provable [duplicate]
To decide whether a propositional formula $P$ is classically provable, the completeness theorem gives an easy algorithm : simply test all finite boolean combinations of the variables of $P$. It is ...
0
votes
1answer
36 views
Proof confusion or solving strategy?
I was introduced to a $Claim X$ for which the proof involved the use of the Truth of $Claim Y$, later I found a proof to $Claim Y$ (from a different source) and was suprised to find that it involved ...
2
votes
2answers
71 views
How to designate that a proposition is semantically true?
The question is more about mathematical notation I guess. In logic we can designate that a conclusion $B$ is (syntactically) deducible from the premises $A$ by:
$A_1...A_i ⊢ B$
If the above is true ...
5
votes
3answers
64 views
Need to prove $(p \land q) \land (\lnot p \lor r) \rightarrow (q \lor r)$ is a tautology.
I need to prove the following expression is a tautology using propositional logic laws.
My current working out is as follows [not sure if it is correct]:
$$(p \land q)\land ( \lnot p \lor r) \...
1
vote
1answer
43 views
Logic equivalents for connectives in SL using only the Sheffer stroke
According to forallx (P.D. Magnus, N.D.) every sentence written using a connective of sentential logic can be rewritten as a logically equivalent sentence using one or more Sheffer strokes $(A \mid B)$...
3
votes
2answers
58 views
Prove $A \implies C$
Given, $(A \lor B) \implies C$, prove $A \implies C$
My Proof:
1 By Conditional Exchange,
$$\neg(A \lor B) \lor C$$
2 By DeMorgan's Law,
$$(\neg A \land \neg B) \lor C$$
3 By Simplification,
$$\...
4
votes
2answers
52 views
Prove $\neg (p \land q) \vdash \neg p \lor \neg q$ by natural deduction
I have tried solving this by negating $\neg p \lor \neg q$ to get to a pbc, but apparently you need to use a few lem's (law of excluded middle) to solve the problem. Where (and how) have I gone wrong ...
1
vote
1answer
54 views
$P → Q$ using only NOR gates [closed]
Not much to say apart from what's in the question. I'm fairly new to logic so help would be much appreciated.
-1
votes
0answers
32 views
Efficient way to create relationships between logical variables?
I'm not well versed in logic, but I know basic logical operators and the corresponding truth tables.
My question is this. Given a set of n variables, how could I symbolically encode the relationships ...
2
votes
2answers
40 views
What's the most efficient way to convert any propositionnal logic formula to DNF
In every paper that I've read so far, authors say that they convert a formula into disjunctive normal form (DNF) but they don't give any detail on how they are doing it.
The only way of converting a ...
0
votes
1answer
45 views
Prove $(\exists x)A\to((\exists x)(A\wedge(B\vee C))\equiv B \vee (\exists x)(A\wedge C))$, if $x$ is not free in $B$
Prove $(\exists x)A\to\big((\exists x)(A\wedge(B\vee C))\equiv B \vee (\exists x)(A\wedge C)\big)$, if $x$ is not free in $B$.
I've tried multiple different ways and I'm not able to see a good path ...
1
vote
4answers
58 views
Prove that if P, then $Q → ¬(Q → ¬P)$
Suppose that $P$ is true. Prove that $Q → ¬(Q → ¬P)$ is true.
My attempt:
If $Q$, then statement $\lnot (Q → \lnot P)$ must be true. We know that $P$ is true. For $¬(Q → ¬P)$ to be true, $Q$ must be ...
2
votes
2answers
59 views
Prove using properties of logical equivalence $(P\wedge (P \to (Q \to R))) \to (Q \to R)$ is a tautology
Can anyone help me with this problem using properties of logical equivalence:
Prove that $(P\wedge (P \to (Q \to R))) \to (Q \to R)$ is a tautology.
1
vote
2answers
57 views
Question: Is This a Proposition?
Every positive even integer can be written as the sum of two primes.
The answer is: this is a proposition. Nobody knows its truth value, but it's unique.
I wonder what is unique and why its ...
1
vote
2answers
49 views
Symbolic Logic Proof — Typo?
I was working through some proofs in my symbolic logic book when I came across the following problem:
$$\text{Given:}$$
$$\\ (A \lor B) \implies(C \lor D)$$
$$\\ (C \implies W) \land (D \implies \neg ...
2
votes
1answer
67 views
Vacuous Truths and Continuity at a Point Where a Map is Undefined
I understand that a conditional statement is said to be vacuously true in the case that its antecedent is false, in which case the conditional statement is, itself, true. However, what about the ...
0
votes
0answers
24 views
Propositional formula proof by resolution
I am having issues with proving by resolution the follow propositional formula:
$(ψ_1 ∧ ψ_2) → ψ_3$ where
$ψ_1 = (p → (q ∨ r)) ∧ (q → (r ∨ p)) ∧ (r → (p ∨ q))$
$ψ_2 = ((p ∧ q) → r) ∧ ((q ∧ r) → p) ∧...
1
vote
0answers
28 views
How can I simplify this proposition where 4 out of 5 values are true and the remaining 1 out of 5 is false?
I am fairly new to logic and I am curious as to whether it is possible to simplify this proposition where 4 out of 5 values must be true and one of them has to be false.
(P1 ∧ P2 ∧ P3 ∧ P4 ∧ ¬P5) ∨ (...
1
vote
1answer
76 views
How to formalize this simple problem in logic?
I want to translate this problem with a simple logical expression.
Say that my system only accepts tuples of strings $(s=s_1...s_n$, $t=t_1...t_n)$ where $s_i$ and $t_i \in \{0, 1, 2\}$, that are ...
2
votes
4answers
40 views
Prove that $(\neg P \lor Q)\wedge (P \lor \neg R)\wedge (\neg P \lor \neg Q)$ and $\neg (P \lor R)$ logically equivalent.
Q. Prove that $(\neg P \lor Q)\wedge (P \lor \neg R)\wedge (\neg P \lor \neg Q)$ and $\neg (P \lor R)$ logically equivalent.
I can get a feel for why this will be true.
My argument goes as follows:
...
1
vote
2answers
58 views
Deduction of $\forall x(\neg p(x)\rightarrow q(x)), \forall z(p(z)\rightarrow r(z))\vdash \forall z(\neg r(z) \rightarrow\exists yq(y))$
I trying to study for my final exam and I can't figure out how to solve this:
$\forall x(\neg p(x)\rightarrow q(x)), \forall z(p(z)\rightarrow r(z))\vdash \forall z(\neg r(z) \rightarrow\exists yq(y))...
1
vote
1answer
35 views
Can you replace any Statement in a Tautology?
A few theorems I read somewhere online say that in a tautology, you can replace any statement by another statement to get another tautology. For instance, we have the following tautology:
$[A \land (...
0
votes
1answer
15 views
Absorption's Law - Negative proposition affects the law?
This is a simple question.
It's known that the absorption's law is like the following example:
p ∧ (p V q) = p
But, if the proposition has a negation, does this affect the law?
for example:
p ∧...
