Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.
4
votes
1answer
62 views
Which law of logical equivalence says $P\Leftrightarrow Q ≡ (P\lor Q) \Rightarrow(P\land Q)$
I'm going through the exercises in the book Discrete Mathematics with Applications. I'm asked to show that two circuits are equivalent by converting them to boolean expressions and using the laws in ...
0
votes
1answer
41 views
Propositional Logic “Riddle/Puzzle”
I have this kind of 'riddle' as a question that i need to complete, however I'm not sure what to do of it.
This is the question:
...
1
vote
1answer
53 views
What does $\vdash s \rightarrow (\neg s\rightarrow t)$ mean?
What does this statement mean $\vdash s \rightarrow (\neg s\rightarrow t)$?
And how can I prove it?
0
votes
2answers
40 views
what is the diffrence between a term , constant and variable in first order logic languages ?
in the text , the author says that the language contains parenthises , sentintial connectives and n-place functions , n-place predicates , equality sign = , terms , constans and variables
i have two ...
-2
votes
1answer
46 views
How to prove that a set of connectives aren't adequate
I guess we have to prove it somehow by an induction as I saw a few examples online. But it just makes absolutely no sense to me... Can somebody explain it in human language? Thank you very much.
0
votes
1answer
35 views
Regularity of balanced binary strings
How can one tell which number of propositional variables is necessary
to express a Boolean function given as a sequence of 0s and 1s (a
binary string) of length $2^n$ as a Boolean formula?
...
0
votes
1answer
60 views
if $p\implies q$ is the same as $\lnot p \lor q$, then…
If $p\implies q$ is the same as $\lnot p \lor q$, then what is $p\implies \lnot q$?
I'm not sure if this is $\lnot p \lor \lnot q$, or $\lnot p \lor q$.
I'm trying to figure this out, because i have ...
1
vote
1answer
34 views
Appearance of sentence parameters in a theorem
Is it true that if $A$ is a formula in a Hilbert system $H$, then if $B_1,B_2,\ldots,B_n$ is a proof of $A$ in $H$, any sentence parameter not appearing in $A$ doesn't appear in $B_1,\ldots,B_n$? If ...
3
votes
2answers
57 views
Is there a difference between 'inconsistent', 'contrary', and 'contradictory'
Is there a difference between 'inconsistent' 'contrary' and 'contradictory'? As far as I understand, two statements are inconsistent when they can not both be true; two statements are contradictory ...
1
vote
1answer
69 views
-7
votes
0answers
47 views
3
votes
0answers
39 views
Boolean combinatorics
Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i ...
4
votes
2answers
77 views
Deriving A implies B from Not A
My logic textbook has the following example showing how to derive $A \to B$ from $\neg A$:
First we assume $A$ and use the conjunction introduction rule which results in a contradiction $[A] \land ...
1
vote
2answers
88 views
Do the premises logically imply the conclusion?
$$b\rightarrow a,\lnot c\rightarrow\lnot a\models\lnot(b\land \lnot c)$$
I have generated an 8 row truth table, separating it into $b\rightarrow a$, $\lnot c\rightarrow\lnot a$ and $\lnot ...
1
vote
4answers
74 views
Writing an expression using logic
Write an expression using letters $\land, \lor, and$ $\neg$ which has the following truth table:
$$\begin{array}{ccc|c}
P&Q&R&???\\ \hline
T&T&T&F\\
T&T&F&T\\
...
0
votes
3answers
69 views
what is the relation between not A and everything but A
I am examining Bayes' Theorem, and wondering about the alternative interpretations of ~A, as being:
not A, ¬ A
everything but A, ∀-A
And how this will affect the use of probabilities.
...
2
votes
2answers
57 views
Are these propositions equivalent?
Statement 1: Maria will find job if she learns mathematics.
Statement 2: Maria will find a job unless she does not learn
mathematics.
I know the answer is probably that these are same, but ...
3
votes
1answer
34 views
Boolean Algebra Transform
I am revisiting Boolean algebra after a long while.
Can somebody help show me how to simplify the LHS to get the RHS?
$$abc * a'bc + (abc)' * (a'bc)'\quad = \quad \;b'+c'$$
2
votes
3answers
65 views
Logic Negation Symbols
This is a rather simple question but I can't find an exact answer on it...
In examples I've seen, i've seen the ~ symbol and the ¬ symbol. These fall under 'negation'. if they both fall under ...
1
vote
0answers
46 views
Can any axiom of a first order mathematical theory be written as a definition?
I have seen different axiomatizations of PA. I some, equality is defined in others is an axiom. The same can be said of addition and multiplication. So it is not clear to me why and when axioms are ...
1
vote
1answer
70 views
Logical correlation from Oedipus myth
My girlfriend likes the myths and she found an MIT article about Oedipus myth which is looks interesting for her. She showed me, but for me it is looks like no correlation between the logical ...
2
votes
2answers
69 views
Every sentence in propositional logic can be written in Conjunctive Normal Form
While reading through Artificial Intelligence - A Modern Approach by Stuart Russell and Peter Norvig, I came upon the following ...
1
vote
1answer
43 views
Simple logic equivalence incorrect
I am having some problems negating a rather simple logical statement. I am currently taking a introduction course, so please bear with me if my question is silly.
I am supposed to turn this:
$$ ...
1
vote
1answer
41 views
In Fitch, is a symbol not in a specified language automatically free?
In Fitch proofs where no language has been specified, we (at least seem to) treat lines that have the form
$$p(x)$$
to mean that $x$ "can be anything". That is they are equivalent to
$$\forall ...
4
votes
1answer
54 views
distribution of categorical product (conjunction) over coproduct (disjunction)
In the classical and intuitionistic propositional calculi, it is straightforward, using natural deduction, to derive $((A \land C) \lor (B \land C))$ from $(A \lor B) \land C$:
Assume $(A \lor B) ...
1
vote
1answer
37 views
Less absorption in Minimal Logic?
I just wonder whether the following is not derivable in Minimal Logic:
$$ \bot \dashv\vdash \bot \land A \hspace{3em}\mbox{/* not derivable */ }$$
I read this that although Minimal Logic attaches ...
2
votes
3answers
51 views
Use rules of inference to show
Premises:
$p \land \lnot s$
$q \to (r \to s)$
Conclusion:
$(p \to q) \to \lnot r$
Use rules of inference to show the above argument is valid.
I only manage to get $(p \to q) \to (p \land ...
1
vote
0answers
53 views
Equivalence of two very specific propositional calculi
Let $H$ and $L$ be two propositional calculi. $H$ has as inference rule modus ponens only, and three axiom schemes:
P1: $A\rightarrow . B\rightarrow A$
P2: $(A\rightarrow . B\rightarrow ...
0
votes
1answer
29 views
continuous function question
Assume that function $f$ is continuous at $x=0$. Prove that the function
$f(x)=a^x$
for $a>0 $, is continuous at every real number.
I know that $f$ is continuous at 0 if and only if 0 is in the ...
1
vote
1answer
33 views
Getting the CNF and DNF (Logic)
I have a function:
$$A = \lnot \left(p \rightarrow \lnot(q\lor r)\right)$$
Simplifying it, the DNF of the Function is
$$(p \land q) \lor (p \land r)$$
How do I get the CNF of this function?
0
votes
3answers
39 views
Implication review!
I am currently studying for my Discrete Structures final exam, and there is a question I am not sure how to answer...
Question is:
Consider the following implication.
"If i do not debug the ...
0
votes
1answer
51 views
Infinite number of Proofs in Propositional Calculus?
Reading over a book on computability, it asserts that in P.C., if A is a theorem, then A has arbitrarily many proofs. I can't see how that would work, would you do an infinite loop in the sequence of ...
1
vote
2answers
128 views
Predicate Logic Argument Validity
My question is whether or not the following is a validly structured argument:
(P→T)→Q
Q → ¬Q
∴ P
I'm getting hung up on the Q→¬Q part by itself as a premise, it doesn't seem like that is ...
1
vote
2answers
57 views
Simplify a proposition
I can not come up with anything concrete,
$$ [\overline{(p \wedge q)} \wedge r] \vee [p \wedge \overline{( q \wedge r)}] \Leftrightarrow \, ? $$
Thanks!
1
vote
2answers
81 views
Prove a tautology using truth table
How do I prove $(\lnot p \rightarrow F)\rightarrow (p=T)\;$ using a truth table?
(This tautology symbolizes a "proof by contradiction". If p being false leads to a contradiction, then p is true.)
3
votes
2answers
90 views
Counterexample in propositional logic
There is this lemma: Let $\Sigma\subset \textrm{Prop}(A)$ and $p, q \in \textrm{Prop}(A)$. Then $\Sigma\models p \implies \Sigma\models p\vee q$. I can't figure out a counterexample for the opposite ...
4
votes
4answers
221 views
Counterexample for $(p\rightarrow q) \longleftrightarrow (!q \rightarrow\mathord !p) $
Is the statement $$(p\rightarrow q) \longleftrightarrow (!q \rightarrow \mathord!p) $$ always true? If it is not, provide a counterexample.
Till now I cannot find a counterexample nor prove that ...
2
votes
2answers
65 views
is this argument true?
i had a puzzle and used a logical argument to show a point but some says that my argument is wrong but i can't understand the reason they provide !
the puzzles says ,
Given four cards laid out on a ...
2
votes
2answers
75 views
How to prove that $(A \lor B) \land (\lnot A \lor B) = B$
I know this is fairly basic, and I understand that it becomes
$$
\begin{align}
(A \land \lnot A) \lor B \\
F \lor B \\
B
\end{align}
$$
However, I can't work out how to prove that it becomes that ...
23
votes
16answers
2k views
In classical logic, why is$ (p\Rightarrow q)$ True if both p and q are False?
I am studying entailment in classical first-order logic.
The Truth Table we have been presented with for the statement $(p \Rightarrow q)\;$ (a.k.a. '$p$ implies $q$') is:
...
9
votes
2answers
146 views
What is the converse of this statement and is it true?
If $a$ and $b$ are relatively prime, $a\mid c$ and $b\mid c$, then $(ab)\mid c$.
I am lost. Would the converse be "If $(ab)\mid c$, then $a$ and $b$ are relatively prime and $a\mid c$ and $b\mid c$" ...
0
votes
0answers
18 views
First order logic - Proof: z is valid under structure S iff not z is not satisfiable
This is what I want to prove:
Prove that: formula $z$ is valid in $S$ if and only if $\lnot z$ is not satisfiable in $M = (D,I)$.
This is my attempt:
Consider $z$ valid in $M$. Consider ...
0
votes
2answers
47 views
Propositional logic “equivalent to” using union, intersection and negation
In the Maths book, "implies to" is described as
$A\rightarrow$B equals to $\lnot\ A \lor B $
How can I represent $A \Leftrightarrow B$ in the same way?
4
votes
2answers
110 views
Why is propositional logic not Turing complete?
According to 1 (probably not the most relevant source), propositional logic is not Turing complete. Aren't all computations in computers performed using logic gates, which can be represented as ...
4
votes
1answer
88 views
Is this expression true and legal?
I want to write it simple and easy but I'm not sure about precedence
A→B & NOT A→ NOT B ↔ NOT A XOR B = 1
I want to express
((A→B) & (NOT A→ NOT B)) ↔ (((NOT A) XOR B)) = 1
Are the two ...
5
votes
3answers
132 views
Modus Ponens vs implication?
What is the difference between Modus Ponens and an implication?
If so, could you please give a simple example to help understanding?
5
votes
5answers
2k views
Associativity of logical connectives
According to the precedence of logical connectives, operator $\rightarrow$ gets higher precedence than $\leftrightarrow$ operator. But what about associativity of $\rightarrow$ operator?
The implies ...
5
votes
1answer
183 views
In axiomatization of propositional logic, why can uniform substitution be applied only to axioms?
I'm reading an introductory book about mathematical logic for Computation (just for reference, the book is "Lógica para Computação", by Corrêa da Silva, Finger & Melo), and would like to ask a ...
2
votes
3answers
219 views
Find an equivalent to $(P \lor Q) \land (P \to R) \land (Q \to S)$
I need some help regarding solving a logic. The question is to find an equivalent to the following logic.
$$(P \lor Q) \land (P \to R) \land (Q \to S)$$
The choices are
(a) $S \land R$
(b) $S ...
0
votes
0answers
36 views
a problem in understanding the proof of recursion theorem ?
there is some problem in understanding the proof of recursion theorem in the text , mathematical introduction to logic by enderton page 44 ,
we have a set U and a subset B of U and C is the subset ...
