Tagged Questions
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 ...
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 ...
-3
votes
1answer
50 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.
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
60 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 ...
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
70 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
58 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
66 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
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
71 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
71 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
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
55 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 ...
1
vote
1answer
37 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
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
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!
3
votes
2answers
91 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 ...
1
vote
2answers
83 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.)
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 ...
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 ...
5
votes
3answers
133 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?
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 ...
1
vote
0answers
27 views
Structural Induction: Base case leads to a contradiction
To make my question clear, I will start with some definitions and notation from the book I am studying:
Definition:
A function $\theta$ from the set of formulas into the set of formulas is a ...
2
votes
1answer
68 views
What is the difference between $Γ⊭Φ$ and $Γ⊭¬Φ$?
Did I understand this correctly?
$Γ⊨Φ$ ($Φ$ is considered true)
$Γ⊨¬Φ$ ($Φ$ is considered false)
$Γ⊭Φ$ ($Φ$ is considered neither true nor false)
$Γ⊭¬Φ$ ???
Please help me understand. How can ...
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 ...
1
vote
2answers
41 views
Need help with solving proposition logic formula, should be a tautology
I have the following formula:
$(((p \vee q) \rightarrow r) \wedge (p \rightarrow q))\rightarrow (q\rightarrow r)$
The truth table for this formula shows that this is a tautology. However, I get ...
2
votes
2answers
95 views
Is it true that $((A\rightarrow B)\land(¬A\rightarrow ¬B))↔((¬A) \;\;\text{⊕}\;\; B)$? [closed]
Is $((A\rightarrow B)\land(¬A\rightarrow ¬B))↔((¬A) \;\;\text{⊕}\;\; B)$ true? I found it's true but I don't know what to use it for besides refactoring. How interesting is the statement A→B if not ...
2
votes
3answers
119 views
Exercise in propositional logic.
Which of the following arguments is valid?
A. If it rains, then the grass grows. The worms are not happy unless it rains. Therefore, If the worms are happy , then the grass grows.
B. If the wind ...
2
votes
2answers
76 views
Propositional Calculus Questions
I have a few questions that I am working on, that I supposedly answered incorrectly.
I have the following statements that I am charged to express in symbolic form:
$f =$ you are a full-time student; ...
3
votes
3answers
467 views
De-Morgan's theorem for 3 variables?
The most relative that I found on Google for de morgan's 3 variable was: (ABC)' = A' + B' + C'.
I didn't find the answer for my question, therefore I'll ask here:
...
6
votes
5answers
249 views
How to demystify the axioms of propositional logic?
How might I go about getting some intuition on the typical axiom schemes given for propositional logic? They seem rather mysterious at first glance.
For example, these are taken from: ...
1
vote
2answers
80 views
3
votes
1answer
69 views
What does it mean that a set S tautologically implies wff $\tau$
What does it mean that a set $S$ tautologically implies wff $ \tau$ ?
in Enderton introduction to mathematical logic , in page 23 ,
it define that a set $S$ tautologically implies wff $ \tau$ iff ...
4
votes
2answers
122 views
a good text for a first course in mathematical logic
in last two months , i asked many people about good text for first mathematical logic .
after that a chose some text , first order mathematical logic , angelo magrais ,
it is ok but the text uses ...
0
votes
1answer
54 views
what is the difference between formula and the abbrevation of a formula?
there is a problem which is asking me to determine whether a string is a formula or an abbrevation of a formula
but i don't know the diffrence of formula and the abbrevation of a formula
i know ...
1
vote
2answers
93 views
what is the definition of an interpretation of first order theory $T$ ? what is a model for $T$?
what is the definition of an interpretation of first order theory $T$ ? what is a model for $T$ ?
can you give me the definition supported with some simple examples ?
i read the definition in ...
