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,467
questions
0
votes
0
answers
26
views
propsitional logic exersice
Show that [(p ∨ q) ∧ (r ∨ ¬q)] → (p ∨ r)] is a tautology by making a truth table, and then again by using an argument that considers the two cases “q is true” and “q is false”
I need help on this one ....
- 19
1
vote
0
answers
31
views
Uniform continuity and the order of quantifiers
I’m taking my first course in real analysis, and I’m trying to prove the following proposition.
Proposition:
If $f:S\to\mathbb{R}$ is uniformly continuous, then $f$ is continuous.
In comparing ...
- 101
2
votes
1
answer
126
views
Open source program that generate "random" theorems by exploration
With some formal systems, it's possible to enumerate all the theorems.
This is the case for instance in propositional calculus or in some first-order theories with a recursively enumerable set of ...
- 471
1
vote
1
answer
51
views
Can this disjunction be eliminated?
This is a question about classical propositional logic.
Definitions: If there is a proof from $\alpha$ to $\beta$, we'll write $\alpha \vdash \beta$. We'll say that $\alpha$ is equivalent to $\beta$ ...
- 1,690
1
vote
3
answers
99
views
How does propositional logic address the situation where the statement $(p \Rightarrow q)$ is false?
I was exploring the inferences drawn from the truth values of $p$, $q$, and $(p \Rightarrow q)$. The truth table of material implication is:
$$\begin{array}{|c|c|c|}
\hline
p&q&p\Rightarrow q\\...
- 908
0
votes
0
answers
18
views
Satisfiability of clauses of the form "At most m out of n are false"
Recall some terminology: Let $\mathsf P$ be a finite set of propositional atoms, and let $\Phi$ be a proposition over $P$ that is generated from $\top$, $\bot$, $\neg$, $\wedge$, and $\vee$. Then:
A ...
- 446
0
votes
0
answers
42
views
Is the logic $\mathsf{wK4}$ plus Lob's rule the same as $\mathsf{GL}$?
Let $\mathsf{wK4}$ be the logic of weak transitive frames and $\mathsf{GL}$ be the provability logic.
It is well-known that one can define $\mathsf{GL}$ as $\mathsf{K4}$ (the logic of transitive ...
- 154
0
votes
0
answers
15
views
Do sole sufficient operators have to abbreviate existing functions?
I'm thinking about this question about modal logic.
I'm wondering whether a sole sufficient operator needs to be an abbreviation of existing functions or not.
More concretely, consider an equational ...
- 10.2k
3
votes
2
answers
160
views
You forgot whether the logic class is at 11 or 12. Your friend knows which but sometimes lies. What should you ask them?
In "Mathematical Logic" by Chiswell and Hodges, there is the following exercise (3.5.3):
You forgot whether the logic class is at 11 or 12. Your friend certainly knows which; but sometimes ...
0
votes
0
answers
24
views
The number of left parentheses is greater than or equal to the number of right parentheses. [duplicate]
Using induction on the complexity of formulas, let's assume that in every proper non-empty initial segment of a propositional formula, the number of left parentheses is greater than or equal to the ...
- 25
2
votes
1
answer
66
views
How to prove the tautology for the inference rule of hypothetical syllogism using a chain of logical identities?
Let $p$, $q$, and $r$ be any propositions. Then, using a chain of logical equivalences, how to establish the following logical identity?
$$
\big( (p \rightarrow q) \land (q \rightarrow r) \big) \...
- 26.2k
1
vote
1
answer
55
views
Rule to calculate derivative of function which is a binary operation between two other functions.
Let $\mathbf{g}:\mathbb R\rightarrow \mathbb R$ be a differentiable function defined as $g(x)=f(x)*h(x)$ where $*$ is any binary operation between the two differentiable functions $\mathbf{h}:\mathbb ...
- 133
4
votes
2
answers
167
views
Given a $P$ does this always imply either $Q$ or $\neg Q$? (not both at the same time)
Given a $P$ does this always imply either $Q$ or $\neg Q$?
I want to show that given a $P$, then either $Q$ holds or $\neg Q$ holds (that is, not both at the same time).
My attempted proof is the ...
- 191
2
votes
1
answer
49
views
Is Resolution Intuitionistically Valid?
Specifically, is it intuitionistically valid to deduce $Q$ from $P\vee Q$ and $\neg P\vee Q$? The proof I could come up with uses the law of exclusive middle, and I feel that you can probably come up ...
- 1,559
1
vote
2
answers
91
views
Proof of contraposition theorem using logical (semantic) entailment definition
I have been reading some older course material from Propositional Logic and I stumbled on a question, and I am unsure on how to start the proof. The question is:
Prove the following theorem (...
- 13
1
vote
1
answer
20
views
Finding a Proposition to Satisfy Given Logical Statements
I'm facing a logical inference problem and seeking guidance to find a proposition p3 that satisfies certain logical conditions.
Given propositions:
p1 = p or r
p2 = q => !p
p3=?
Given conclusions:
...
- 59
0
votes
2
answers
104
views
Can a English statement be expressed as more than one logical expression, both of which mean the same thing?
Consider
$P(x,y)$: $x$ is a citizen of $y$.
$Q(x,y)$: $x$ lives in $y$.
The universe of discourse of x is the set of all people
The universe of discourse of y is the set of US states.
Express the ...
- 11
-3
votes
0
answers
35
views
Seeking Guidance on Logic Gate Configuration for Desired Truth Table Outcome
I'm working on a logic gate configuration problem and could use some guidance. The goal is to determine which logic gates should be used between B and C, as well as between the result of B and C (let'...
2
votes
3
answers
100
views
How to express an invalid argument such as "affirming the consequent" in propositional logic?
For example, say you want to write a symbolic statement for affirming the consequent. You could write it in the following two ways
$$
(P \to Q, Q) \to P
$$
or
$$
\frac{P \to Q, Q}{P}
$$
Which one ...
- 556
1
vote
1
answer
48
views
What are good examples of counterintuitively non-antilogical formulae?
This post is not about counterintuitive tautologies, but about conterintuiitive contingent formulae.
Easy examples of formulae that ( probably) are counterintuitively non-antilogical are : $ \neg A \...
- 1,613
0
votes
2
answers
63
views
How to translate this sentence into propositional logic?
How to translate this sentence into propositional logic?
Because it is dark outside, I cannot see anything.
Let us take
$$
\begin{align}
p &\colon \mbox{ It is dark outside}, \\
q &\colon \...
- 26.2k
5
votes
4
answers
195
views
On the tautology $(P \implies Q) \vee (Q \implies P)$
The logical statement
$$(P \implies Q) \vee (Q \implies P)$$
is an example of a tautology. However, if I choose logical statements for $P$ and $Q$, it is not always true that either $Q \implies P$ or $...
- 119
0
votes
1
answer
86
views
Formalizing Real World Sentence In Intuitionistic Logic?
In my local supermarket, there is a notice with a recall, in the end it says:
This warning does not imply that the damage was caused by the producer, manufacturer, importer, or distributor
My first ...
- 3,522
0
votes
1
answer
82
views
Enderton's "Mathematical Introduction to Logic": Is he proving second order induction?
I am reading Enderton's "Mathematical Introduction to Logic" and I am puzzled by the following reasoning:
Enderton defines the symbols of propositional logic (sentence letters and ...
- 520
3
votes
2
answers
67
views
Propositional formula
how can I transform this statement into a propositional formula?
Theseus must die on Skyros, or else Skyros will be devastated
What symbol is "or else", I can't find anything on the internet....
- 39
0
votes
0
answers
31
views
Propositional Logic in Prolog - Incorrect Representations
There is a certain premise which I am unable to represent correctly as propositional logic:
"When I play basketball, I wear my sneakers; otherwise, I never wear it."
...
0
votes
0
answers
12
views
How to prove that a proposition with non reappearing variables can't be a tautology or contradiction? [duplicate]
I have to prove that a propsitional formula can't be a contradiction, when every variable in it appears only once.
Our definition of a propsitional formula is as follows:
A propositional formula is ...
- 325
2
votes
1
answer
69
views
Need of hypothesis and counter-example
I have a theorem in the form : if A is verified and B is verified and C is verified then D is verified.
I'd like to show that we can't do without hypothesis C.
How can I do this?
Do I need to find an ...
- 145
0
votes
0
answers
36
views
How do I translate this sentence into propositional logic notation? [duplicate]
If one were to translate a sentence in the form of "p, but q" into propositional logic notation, would they write "p -> q", or "p v q"?
0
votes
2
answers
74
views
Intuitive answer doesn't match with logical reasoning I used
I'm Trying to see validity of the following argument:
If i get chirstmas bonus, I'll buy stereo
If i sell my motorcycle, I'll buy stereo
therefore if i get a christmas bonus or I sell my motor ...
0
votes
1
answer
89
views
Natural deduction with $(A→B)→C, A∧B ⊢C$
$(A → B) → C, A ∧ B \vdash C$
1.$\hspace{1cm}(A → B) → C \hspace{1cm}$premise
2.$\hspace{1cm}A ∧ B \hspace{2.5cm}$ premise
$\hspace{2cm}$ 3. $\hspace{1cm} A \to B \hspace{1cm}$ Assumption
$\hspace{2cm}...
- 1,015
0
votes
0
answers
61
views
Is this natural deduction proof of $\exists x \neg Px \vdash \neg \forall x Px$ correct?
When it comes to proofs there is no way to tell whether I have done correct or not. In the solution they did in another way which makes me wonder if this correct? For future question, how can I verify ...
- 1,015
-1
votes
2
answers
48
views
7
votes
3
answers
982
views
What exactly does $X - (Y ∪ Z)$ mean?
Does the above mean:
$x$ is in $X$ but [$x$ is not in $Y$ or $x$ is not in $Z$]
OR
$x$ is in $X$ but [$x$ is not in $Y$ and $x$ is not in $Z$]
?
- 113
1
vote
1
answer
38
views
Provide an interpretation where a formula $\forall x \exists y G(x,y) \wedge \neg \exists z G(z,z)$ of predicate logic holds true
Provide an interpretation where $∀_{x}∃_{y}G(x,y) ∧ ¬∃_{z}G(z,z)$ holds.
G(x, y) = x "greater than" y
This gives us the meaning that for all numbers, there exists a number where x is ...
- 1,015
1
vote
1
answer
88
views
Is this natural deduction proof of $\exists x Fx \to G \vdash \forall x [Fx \to G]$ in predicate logic correct?
Like the title says, is this correct?
Edit I left out a big detail: G is a closed formula (meaning it does not contain x as a free variable).
- 1,015
1
vote
0
answers
40
views
Did I do this propositional logic proof correctly?
This is how I have tried to solve it but I have no answer sheet to check whether I did correct or not.Is this correct?
$q→r, p ⊢ (p→q)→(r∧q)$
- 1,015
0
votes
1
answer
65
views
How to use predicate logic to write "Product of an even number and another number is even"?
So this is the correct solution where $U(x)$ means "odd" but personally I only did it with one of them , as in , I didn't use the or-statement to show "when either $y$ is even or $z$ is ...
- 1,015
2
votes
2
answers
172
views
Seeking a More Efficient Solution for Knights and Knaves Logic Puzzle
I am working on a Knights and Knaves logic puzzle, and I have formulated a solution using a truth table. However, I'm wondering if there's a more efficient or faster way to arrive at the solution ...
- 59
5
votes
0
answers
91
views
Prove that every tautology of the form (α → β) can be broken into (α → γ) and (γ → β), where the variables in γ aren’t in exactly one of α and β
Given a tautology of the form (α → β), where α and β are propositions, I want to prove that there exists another proposition γ such that (α → γ) and (γ → β) are both tautologies, and that γ can only ...
- 51
0
votes
2
answers
129
views
How to prove with natural deduction?
Given this question, I tried solving in the first picture as you can see, but I didn't know how to continue and the second image is the right way to solve it. My question is have I done right so far? ...
- 1,015
0
votes
0
answers
51
views
Propositional logic: Natural deduction
Is the first solution valid? If not, can someone explain to me why the first solution is not valid but the second one is? Both claim that p and not p is true though?
$\lnot p \to p \vdash p$
$1 \...
- 1,015
1
vote
1
answer
36
views
Existence of non-satisfiable set of n propositions with all proper subsets satisfiable, for all n in N
I'm trying to prove that for all $n \in N$, there is a set of $n$ propositions $\Sigma_n$ such that all of its proper subsets are satisfiable but $\Sigma_n$ itself is not satisfiable. All propositions ...
- 13
1
vote
0
answers
106
views
Has this logic already been studied?
I have been spending the better part of a year thinking about the subtleties involved in balancing natural language intuitions for logic with the power and efficacy that Classical Logic and ...
- 993
0
votes
0
answers
45
views
Syntactic proof: If Γ, ϕ ⊢ Θ and Γ, ¬ϕ ⊢ Θ then Γ ⊢ Θ
How can I prove this syntactically: If Γ, ϕ ⊢ Θ and Γ, ¬ϕ ⊢ Θ, then Γ ⊢ Θ?
If I weren't constrained by a particular formal system (see below), I think I could use the deduction theorem to first derive ...
- 375
1
vote
0
answers
36
views
Prove the following lemma of propositional logic: (A1 ∨ · · · ∨ Ak) ∧ (A1 → B) ∧ · · · ∧ (Ak → B) |= B. [duplicate]
How do I prove the following lemma of propostional logic:
$(A_1 \vee \ldots \vee A_k) \wedge (A_1 \rightarrow B) \wedge \ldots \wedge (A_k \rightarrow B) \vDash B$
I tried proving it with induction. ...
- 19
2
votes
1
answer
67
views
Gödel's theorems, Löb's theorem, difference between "proves" and "implies"
Layman reading up on Gödel's theorems. I think I have some basic idea of how it all works in the abstract, but I'm still having a hard time distinguishing between (or even counting) the concepts ...
- 591
1
vote
0
answers
56
views
A technique for weakening a universally quantified statement
In a recent question I was investigating (I will not disclose the question here, but will provide some analogous examples) I was trying to apply a certain restricted concept to a broader context. This ...
- 2,125
0
votes
1
answer
90
views
How to do proof by contradiction? [duplicate]
I am taking an introduction to proving class right now and I am confused on how to do a proof by contradiction. If I am trying to prove an implication $(p \to q)$ would it take the form:
suppose $p \...
- 37
2
votes
0
answers
30
views
Recursion theorem in Boolean valued propositional logic [closed]
My question is quite simple: is Boolean valued prop logic a special case of the recursion theorem?
So, we have a finite set of propositional variables, inductive set of formulas constructed by some ...
- 21